aiqbench analysis
This paper establishes minimax-optimal PAC bounds for learning in Markov decision processes with exogenous contexts, offering rigorous theoretical guarantees for policy evaluation and extraction under specific sampling budgets. By decoupling sample complexity from the cardinality of the context space, it provides a significant theoretical advance for reinforcement learning algorithms operating in environments where external factors influence rewards and transitions.
Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
arXiv:2606.25170v2 Announce Type: replace-cross Abstract: We introduce a PAC framework in which the learner can access sampling oracles both before and at decision time. Sample complexity is measured by a pair $(n,m)$, where $n$ is the learning budget spent before a query is known and $m$ is the additional sampling budget per query. We demonstrate its relevance in discounted Markov decision processes with exogenous i.i.d.\ contexts revealed before acting. Contexts may affect both rewards and transitions but remain uncontrolled by the agent. The learner can sample the unknown context distribution and the transition kernel. We study policy evaluation (PE), best-value estimation (BVE), and best-policy extraction (BPE). When rewards and transitions are known, a variance-reduced algorithm solves all three tasks with sample complexity $\bigl(\widetilde O((1-\gamma)^{-3}\varepsilon^{-2}),0\bigr)$, which is minimax optimal up to logarithmic factors. Let $\mathcal{X}$ be the controlled state space. When transitions are also unknown, we give a PE algorithm with complexity $\bigl(\widetilde O(|\mathcal X|(1-\gamma)^{-3}\varepsilon^{-2}), \widetilde O((1-\gamma)^{-2}\varepsilon^{-2})\bigr)$ and matching lower bounds at this budget pair. For BVE and BPE, we give an algorithm with a common offline budget $\widetilde O(|\mathcal X|^2|\mathcal A|(1-\gamma)^{-4}\varepsilon^{-2})$ and respective query costs $\widetilde O(|\mathcal A|(1-\gamma)^{-2}\varepsilon^{-2})$ and $\widetilde O(|\mathcal A|(1-\gamma)^{-3}\varepsilon^{-2})$. Importantly, all bounds are independent of the context-space cardinality.
Abstract:We introduce a PAC framework in which the learner can access sampling oracles both before and at decision time. Sample complexity is measured by a pair $(n,m)$, where $n$ is the learning budget spent before a query is known and $m$ is the additional sampling budget per query. We demonstrate its relevance in discounted Markov decision processes with exogenous i.i.d.\ contexts revealed before acting. Contexts may affect both rewards and transitions but remain uncontrolled by the agent. The learner can sample the unknown context distribution and the transition kernel. We study policy evaluation (PE), best-value estimation (BVE), and best-policy extraction (BPE). When rewards and transitions are known, a variance-reduced algorithm solves all three tasks with sample complexity $\bigl(\widetilde O((1-\gamma)^{-3}\varepsilon^{-2}),0\bigr)$, which is minimax optimal up to logarithmic factors. Let $\mathcal{X}$ be the controlled state space. When transitions are also unknown, we give a PE algorithm with complexity $\bigl(\widetilde O(|\mathcal X|(1-\gamma)^{-3}\varepsilon^{-2}), \widetilde O((1-\gamma)^{-2}\varepsilon^{-2})\bigr)$ and matching lower bounds at this budget pair. For BVE and BPE, we give an algorithm with a common offline budget $\widetilde O(|\mathcal X|^2|\mathcal A|(1-\gamma)^{-4}\varepsilon^{-2})$ and respective query costs $\widetilde O(|\mathcal A|(1-\gamma)^{-2}\varepsilon^{-2})$ and $\widetilde O(|\mathcal A|(1-\gamma)^{-3}\varepsilon^{-2})$. Importantly, all bounds are independent of the context-space cardinality.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2606.25170 [stat.ML]
(or arXiv:2606.25170v2 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2606.25170 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 291 words
Related coverage
Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
arXiv · Jul 24, 2026
Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret
arXiv · Jun 9, 2026
Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation
arXiv · Oct 6, 2026
Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning
arXiv · Jun 3, 2026