1 citations · 1 across the 19 of their papers we have counts for
22 papers
Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
Sasha Voitovych, Adam Block, Alexander Rakhlin +1
Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however,…
Exact simulation of diffusions and improved algorithms for log-concave sampling
Fan Chen, Sinho Chewi, Alexander Rakhlin +1
We study exact simulation of diffusions via rejection sampling on path space using unbiased estimators of the density ratio obtained from Girsanov's theorem. When applied to the un…
Learning with Simulators: No Regret in a Computationally Bounded World
Sasha Voitovych, Abhishek Shetty, Noah Golowich +1
Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some…
The Sample Complexity of Multiclass and Sparse Contextual Bandits
Liad Erez, Fan Chen, Alon Cohen +4
We study contextual bandits in the stochastic i.i.d.\ setting, where a learner observes contexts drawn from an unknown distribution, selects actions from a finite set , and aims…
Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
Fan Chen, Jian Qian, Alexander Rakhlin +1
Self-normalized martingale inequalities lie at the heart of confidence ellipsoids for online least squares and, more broadly, many bandit and reinforcement-learning results. Yet ex…
End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
Zakaria Mhammedi, Alexander Rakhlin, Nneka Okolo
We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying \emph{linear Bellman completeness} -- a fundamental setting w…
Demonstration Experiments
Guido Imbens, Lorenzo Masoero, Alexander Rakhlin +2
Adaptive experiments are used extensively in online platforms, healthcare and biotechnology, and the social sciences. Often, the primary goal is not to precisely estimate a treatme…
Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness
Moïse Blanchard, Abhishek Shetty, Alexander Rakhlin
Understanding minimal assumptions that enable learning and generalization is perhaps the central question of learning theory. Several celebrated results in statistical learning the…
High-accuracy log-concave sampling with stochastic queries
Fan Chen, Sinho Chewi, Constantinos Daskalakis +1
We show that high-accuracy guarantees for log-concave sampling -- that is, iteration and query complexities which scale as , where is the desired target…
High-accuracy sampling for diffusion models and log-concave distributions
Fan Chen, Sinho Chewi, Constantinos Daskalakis +1
We present algorithms for diffusion model sampling which obtain -error in steps, given access to -accurate score estimates in . Thi…
A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
Zeyu Jia, Yury Polyanskiy, Alexander Rakhlin
We study gapped scale-sensitive dimensions of a function class in both sequential and non-sequential settings. We demonstrate that covering numbers for any uniformly bounded class…
Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
Fan Chen, Zeyu Jia, Alexander Rakhlin +1
Reinforcement learning with outcome-based feedback faces a fundamental challenge: when rewards are only observed at trajectory endpoints, how do we assign credit to the right actio…
Trajectory Bellman Residual Minimization: A Simple Value-Based Method for LLM Reasoning
Yurun Yuan, Fan Chen, Zeyu Jia +2
Policy-based methods currently dominate reinforcement learning (RL) pipelines for large language model (LLM) reasoning, leaving value-based approaches largely unexplored. We revisi…
Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective
Zeyu Jia, Alexander Rakhlin, Tengyang Xie
As large language models have evolved, it has become crucial to distinguish between process supervision and outcome supervision -- two key reinforcement learning approaches to comp…
On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
Zeyu Jia, Yury Polyanskiy, Alexander Rakhlin
We study the problem of sequential probability assignment under logarithmic loss, both with and without side information. Our objective is to analyze the minimax regret -- a notion…
Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression
Fan Chen, Jiachun Li, Alexander Rakhlin +1
We study the statistical complexity of private linear regression under an unknown, potentially ill-conditioned covariate distribution. Somewhat surprisingly, under privacy constrai…
Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
Fan Chen, Alexander Rakhlin
We study the problem of interactive decision making in which the underlying environment changes over time subject to given constraints. We propose a framework, which we call \texti…
How Does Variance Shape the Regret in Contextual Bandits?
Zeyu Jia, Jian Qian, Alexander Rakhlin +1
We consider realizable contextual bandits with general function approximation, investigating how small reward variance can lead to better-than-minimax regret bounds. Unlike in mini…
Refined Risk Bounds for Unbounded Losses via Transductive Priors
Jian Qian, Alexander Rakhlin, Nikita Zhivotovskiy
We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression, all characterized by unbounded loss…
Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
Fan Chen, Dylan J. Foster, Yanjun Han +3
We develop a unifying framework for information-theoretic lower bound in statistical estimation and interactive decision making. Classical lower bound techniques -- such as Fano's…
Random Latent Exploration for Deep Reinforcement Learning
Srinath Mahankali, Zhang-Wei Hong, Ayush Sekhari +2
We introduce Random Latent Exploration (RLE), a simple yet effective exploration strategy in reinforcement learning (RL). On average, RLE outperforms noise-based methods, which per…
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…