Online learning in MDPs with side information
Not on the map. Why?
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.
Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 Jun 2014.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 4; 2023: 1; 2024: 0; 2025: 1.
7 papers.
- 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 43
- 2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 17
- 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
- 2022Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regretcited by 3
- 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
- 2022Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximationcited by 2
- 2023Scaling Distributed Multi-task Reinforcement Learning with Experience Sharingcited by 1
- 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewards4 Feb 2025
- 2023Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing11 Jul 2023
- 2022Understanding the Complexity Gains of Single-Task RL with a Curriculum24 Dec 2022
- 2022Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation1 Jun 2022
- 2022Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regret25 May 2022
- 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling15 Mar 2022
- 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs21 Jul 2021