Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
Not on the map. Why?
Abstract (arXiv)
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-γ)-3varepsilon-2),0bigr), which is minimax optimal up to logarithmic factors. Let X be the controlled state space. When transitions are also unknown, we give a PE algorithm with complexity bigl(widetilde O(|mathcal X|(1-γ)-3varepsilon-2), widetilde O((1-γ)-2varepsilon-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-γ)-4varepsilon-2) and respective query costs widetilde O(|mathcal A|(1-γ)-2varepsilon-2) and widetilde O(|mathcal A|(1-γ)-3varepsilon-2). Importantly, all bounds are independent of the context-space cardinality.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 19 of its 30 references that are in the map. First posted on arXiv 23 Jun 2026.
Builds on
19 of 30 references.
References · 19
- 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
- 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
- 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
- 2019Variance-reduced Q-learning is minimax optimalcited by 73
- 2021Navigating to the Best Policy in Markov Decision Processescited by 29
- 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
- 2022Hindsight Learning for MDPs with Exogenous Inputscited by 26
- 2020Privacy-Preserving Dynamic Personalized Pricing with Demand Learningcited by 23
- 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
- 2021Learning to Bid in Contextual First Price Auctionscited by 19
- 2024Reinforcement Learning with Lookahead Informationcited by 8
- 2020Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctionscited by 7
7 more
- 2023Reinforcement Learning with Exogenous States and Rewardscited by 4
- 2023Sample Efficient Reinforcement Learning with Partial Dynamics Knowledgecited by 4
- 2025On the Hardness of Reinforcement Learning with Transition Look-Aheadcited by 4
- 2019The Game of Tetris in Machine Learningcited by 3
- 2024Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learningcited by 3
- 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approachcited by 3
- 2025Timing the Match: A Deep Reinforcement Learning Approach for Ride-Hailing and Ride-Pooling Servicescited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.