104 citations · 270 across the 46 of their papers we have counts for
6 papers · 1 filter
From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson +1
We provide a novel reduction from swap-regret minimization to external-regret minimization, which improves upon the classical reductions of Blum-Mansour [BM07] and Stolz-Lugosi [SL…
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
The key assumption underlying linear Markov Decision Processes (MDPs) is that the learner has access to a known feature map that maps state-action pairs to -dimensiona…
Smooth Nash Equilibria: Algorithms and Complexity
Constantinos Daskalakis, Noah Golowich, Nika Haghtalab +1
A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, in…
On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring
Dylan J. Foster, Dean P. Foster, Noah Golowich +1
A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learnin…
Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games
Dylan J. Foster, Noah Golowich, Sham M. Kakade
We consider the problem of decentralized multi-agent reinforcement learning in Markov games. A fundamental question is whether there exist algorithms that, when adopted by all agen…
Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient
Dylan J. Foster, Noah Golowich, Yanjun Han
A foundational problem in reinforcement learning and interactive decision making is to understand what modeling assumptions lead to sample-efficient learning guarantees, and what a…