# Minimax PAC Bounds for Learning in Exogenous Contextual MDPs

arXiv: https://arxiv.org/abs/2606.25170 · HTML: https://mlsanity.com/paper/2606.25170/

## Key facts

- Cited by 1 papers 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 (most cited first, 19 of 19)

- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Privacy-Preserving Dynamic Personalized Pricing with Demand Learning](https://mlsanity.com/paper/2009.12920/) (2020)
- [Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model](https://mlsanity.com/paper/1806.01492/) (2018)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Reinforcement Learning with Lookahead Information](https://mlsanity.com/paper/2406.02258/) (2024)
- [Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctions](https://mlsanity.com/paper/2002.11349/) (2020)
- [Reinforcement Learning with Exogenous States and Rewards](https://mlsanity.com/paper/2303.12957/) (2023)
- [Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge](https://mlsanity.com/paper/2312.12558/) (2023)
- [On the Hardness of Reinforcement Learning with Transition Look-Ahead](https://mlsanity.com/paper/2510.19372/) (2025)
- [The Game of Tetris in Machine Learning](https://mlsanity.com/paper/1905.01652/) (2019)
- [Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning](https://mlsanity.com/paper/2409.14557/) (2024)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Timing the Match: A Deep Reinforcement Learning Approach for Ride-Hailing and Ride-Pooling Services](https://mlsanity.com/paper/2503.13200/) (2025)

## Built on by (most cited first, 1 of 1)

- [Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead](https://mlsanity.com/paper/2609.11807/) (2026)

## 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.