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 $\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.