Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
Corentin Pla Hugo Richard Marc Abeille Vianney Perchet CREST, ENSAE Criteo AI Lab FairPlay Joint Team Paris, France · 2026
Read Minimax PAC Bounds for Learning in Exogenous Contextual MDPs by Corentin Pla Hugo Richard Marc Abeille Vianney Perchet CREST, ENSAE Criteo AI Lab FairPlay Joint Team Paris, France (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25170.txt.
Introduction
Many decision problems mix a state the agent controls with a context it cannot, like the next piece falling in a Tetris style game. Corentin Pla, Hugo Richard, Marc Abeille, and Vianney Perchet analyse learning in such settings in 2026, asking how many samples provable learning truly needs. Contexts arrive independently from an unknown distribution and can shift both rewards and transitions. Sample use is counted separately before and during execution of the learned policy.
When only the context distribution is unknown, their variance reduced method works with a sample count that never grows with the number of contexts. They prove that rate is best possible up to small factors. Even with transitions also unknown, policy evaluation stays free of context count dependence. Matching lower bounds accompany the main algorithms.
Catalog record
| CREATOR | Corentin Pla Hugo Richard Marc Abeille Vianney Perchet CREST, ENSAE Criteo AI Lab FairPlay Joint Team Paris, France |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 156 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25170