# Online learning in MDPs with side information

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2014.

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

- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Understanding the Complexity Gains of Single-Task RL with a Curriculum](https://mlsanity.com/paper/2212.12809/) (2022)
- [Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling](https://mlsanity.com/paper/2203.08248/) (2022)
- [Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regret](https://mlsanity.com/paper/2205.12418/) (2022)
- [Catoni Contextual Bandits are Robust to Heavy-tailed Rewards](https://mlsanity.com/paper/2502.02486/) (2025)
- [Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2206.00270/) (2022)
- [Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing](https://mlsanity.com/paper/2307.05834/) (2023)

## Abstract (arXiv)

We study online learning of finite Markov decision process (MDP) problems when a side information vector is available. The problem is motivated by applications such as clinical trials, recommendation systems, etc. Such applications have an episodic structure, where each episode corresponds to a patient/customer. Our objective is to compete with the optimal dynamic policy that can take side information into account. We propose a computationally efficient algorithm and show that its regret is at most O(√T), where T is the number of rounds. To best of our knowledge, this is the first regret bound for this setting.