# Learning Efficiently Function Approximation for Contextual MDP

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 21 references that are in the map.
- First posted on arXiv 2 Mar 2022.

## Builds on (most cited first, 4 of 4)

- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Reinforcement Learning in Rich-Observation MDPs using Spectral Methods](https://mlsanity.com/paper/1611.03907/) (2016)
- [PAC Reinforcement Learning with Rich Observations](https://mlsanity.com/paper/1602.02722/) (2016)

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

- [Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP](https://mlsanity.com/paper/2207.11126/) (2022)
- [Eluder-based Regret for Stochastic Contextual MDPs](https://mlsanity.com/paper/2211.14932/) (2022)
- [Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation](https://mlsanity.com/paper/2303.01464/) (2023)
- [Sample Complexity Characterization for Linear Contextual MDPs](https://mlsanity.com/paper/2402.02700/) (2024)
- [Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2206.00270/) (2022)
- [Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximation](https://mlsanity.com/paper/2602.13706/) (2026)
- [Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing](https://mlsanity.com/paper/2307.05834/) (2023)
- [Zero-Shot Context Generalization in Reinforcement Learning from Few Training Contexts](https://mlsanity.com/paper/2507.07348/) (2025)
- [Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards](https://mlsanity.com/paper/2510.20055/) (2025)
- [Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback](https://mlsanity.com/paper/2602.08307/) (2026)

## Abstract (arXiv)

We study learning contextual MDPs using a function approximation for both the rewards and the dynamics. We consider both the case that the dynamics dependent or independent of the context. For both models we derive polynomial sample and time complexity (assuming an efficient ERM oracle). Our methodology gives a general reduction from learning contextual MDP to supervised learning.