New PAC bounds for exogenous contextual MDPs eliminate context dimension dependency

A team of researchers—Corentin Pla, Hugo Richard, Marc Abeille, and Vianney Perchet (Inria)—has published a paper on arXiv that establishes minimax optimal Probably Approximately Correct (PAC) bounds for learning in exogenous contextual Markov decision processes (MDPs). In this setting, at each time step an i.i.d. context is drawn from an unknown distribution and revealed to the agent before it acts. The context influences both rewards and transitions but is uncontrolled by the agent – hence ‘exogenous’.

The authors provide two main contributions. First, when rewards and transition dynamics are known and only the context distribution must be learned, they introduce a variance-reduced algorithm that solves policy evaluation, best-value estimation, and best-policy extraction with a sample complexity of \widetilde{O}\left(1/((1-\gamma)^3\varepsilon^2)\right) – independent of the context space size |Z|. This rate is minimax optimal up to logarithmic factors and also yields tight guarantees for one-step lookahead policies. Second, for the fully unknown regime where both the context distribution and transition kernel must be learned, they show that policy evaluation remains |Z|-free, achieving matching upper and lower bounds of \widetilde{O}\left(|\mathcal{X}|/((1-\gamma)^3\varepsilon^2)\right) before execution and \widetilde{O}\left(1/((1-\gamma)^2\varepsilon^2)\right) during execution. These results resolve a key open theoretical question in contextual reinforcement learning, providing practitioners with guarantees that scale gracefully with problem size.