Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL

2025-02-16 · Matthew Zurek, Yudong Chen

We study the sample complexity of finding an $\varepsilon$-optimal policy in average-reward Markov Decision Processes (MDPs) with a generative model. The minimax optimal span-based complexity of $\widetilde{O}(SAH/\varepsilon^2)$, where $H$ is the span of the optimal bias function, has only been achievable with prior knowledge of the value of $H$. Prior-knowledge-free algorithms have been the objective of intensive research, but several natural approaches provably fail to achieve this goal. We resolve this problem, developing the first algorithms matching the optimal span-based complexity without $H$ knowledge, both when the dataset size is fixed and when the suboptimality level $\varepsilon$ is fixed. Our main technique combines the discounted reduction approach with a method for automatically tuning the effective horizon based on empirical confidence intervals or lower bounds on performance, which we term horizon calibration. We also develop an empirical span penalization approach, inspired by sample variance penalization, which satisfies an oracle inequality performance guarantee. In particular this algorithm can outperform the minimax complexity in benign settings such as when there exist near-optimal policies with span much smaller than $H$.

📄 PDF Abstract BibTeX arXiv:2502.11238

Code (0)

등록된 구현이 없습니다.

Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

2026-05-08 · Idan Attias, Steve Hanneke, Arvind Ramaswami arxiv

Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to exe…

Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?

2024-06-17 · 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 as well as driving many of the recent e…

Binary Classification PAC learning

Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity

2020-07-15 · NeurIPS 2020 12 · Kaiqing Zhang, Sham M. Kakade, Tamer Başar, Lin F. Yang

Model-based reinforcement learning (RL), which finds an optimal policy using an empirical model, has long been recognized as one of the corner stones of RL. It is especially suitable for multi-agent RL (MARL), as it natu…

Model-based Reinforcement Learning Reinforcement Learning (RL)

Sequential Mode Estimation with Oracle Queries

2019-11-19 · Dhruti Shah, Tuhinangshu Choudhury, Nikhil Karamchandani, Aditya Gopalan

We consider the problem of adaptively PAC-learning a probability distribution $\mathcal{P}$'s mode by querying an oracle for information about a sequence of i.i.d. samples $X_1, X_2, \ldots$ generated from $\mathcal{P}$.…

PAC learning

Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting

2020-02-06 · NeurIPS 2020 12 · Ziping Xu, Ambuj Tewari

We study reinforcement learning in non-episodic factored Markov decision processes (FMDPs). We propose two near-optimal and oracle-efficient algorithms for FMDPs. Assuming oracle access to an FMDP planner, they enjoy a B…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)