Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
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 (Õ((1−γ)−3ε−2),0), which is minimax optimal up to logarithmic factors. Let 𝒳 be the controlled state space. When transitions are also unknown, we give a PE algorithm with complexity (Õ(|𝒳|(1−γ)−3ε−2), Õ((1−γ)−2ε−2)) and matching lower bounds at this budget pair. For BVE and BPE, we give an algorithm with a common offline budget Õ(|𝒳|2|𝒜|(1−γ)−4ε−2) and respective query costs Õ(|𝒜|(1−γ)−2ε−2) and Õ(|𝒜|(1−γ)−3ε−2). Importantly, all bounds are independent of the context-space cardinality.
Related
- Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
- Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
- Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs
- Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds
- Minimax bounds for watermarked and masked recursive discrete distribution estimation
BibTeX
@misc{pla2026minimax,
title = {{Minimax PAC Bounds for Learning in Exogenous Contextual MDPs}},
author = {Corentin Pla and Hugo Richard and Marc Abeille and Vianney Perchet},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.25170},
eprint = {2606.25170},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.25170},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
AU - Corentin Pla
AU - Hugo Richard
AU - Marc Abeille
AU - Vianney Perchet
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2606.25170
UR - https://arxiv.org/abs/2606.25170
AB - 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 (Õ((1−γ)^−3ε^−2),0), which is minimax optimal up to logarithmic factors. Let 𝒳 be the controlled state space. When transitions are also unknown, we give a PE algorithm with complexity (Õ(|𝒳|(1−γ)^−3ε^−2), Õ((1−γ)^−2ε^−2)) and matching lower bounds at this budget pair. For BVE and BPE, we give an algorithm with a common offline budget Õ(|𝒳|^2|𝒜|(1−γ)^−4ε^−2) and respective query costs Õ(|𝒜|(1−γ)^−2ε^−2) and Õ(|𝒜|(1−γ)^−3ε^−2). Importantly, all bounds are independent of the context-space cardinality.
ER -