104 citations · 270 across the 46 of their papers we have counts for
10 papers · 1 filter
A Lower Bound on Swap Regret in Extensive-Form Games
Constantinos Daskalakis, Gabriele Farina, Noah Golowich +2
Recent simultaneous works by Peng and Rubinstein [2024] and Dagan et al. [2024] have demonstrated the existence of a no-swap-regret learning algorithm that can reach average sw…
The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
Noah Golowich, Ankur Moitra
In this paper, we study the offline RL problem with linear function approximation. Our main structural assumption is that the MDP has low inherent Bellman error, which stipulates t…
Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions
Noah Golowich, Ankur Moitra
One of the most natural approaches to reinforcement learning (RL) with function approximation is value iteration, which inductively generates approximations to the optimal value fu…
Near-Optimal Learning and Planning in Separated Latent MDPs
Fan Chen, Constantinos Daskalakis, Noah Golowich +1
We study computational and statistical aspects of learning Latent Markov Decision Processes (LMDPs). In this model, the learner interacts with an MDP drawn at the beginning of each…
Online Control in Population Dynamics
Noah Golowich, Elad Hazan, Zhou Lu +2
The study of population dynamics originated with early sociological works but has since extended into many fields, including biology, epidemiology, evolutionary game theory, and ec…
Breaking the Barrier for Sequential Calibration
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson +3
A set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of timesteps where tha…
Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?
Constantinos Daskalakis, Noah Golowich
The empirical risk minimization (ERM) principle has been highly impactful in machine learning, leading both to near-optimal theoretical guarantees for ERM-based learning algorithms…
Edit Distance Robust Watermarks via Indexing Pseudorandom Codes
Noah Golowich, Ankur Moitra
Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which…
On Learning Parities with Dependent Noise
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
In this expository note we show that the learning parities with noise (LPN) assumption is robust to weak dependencies in the noise distribution of small batches of samples. This pr…
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Supervised learning is often computationally easy in practice. But to what extent does this mean that other modes of learning, such as reinforcement learning (RL), ought to be comp…