Online learning in MDPs with side information

Abstract

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(\sqrt{T})$, where $T$ is the number of rounds. To best of our knowledge, this is the first regret bound for this setting.

References in corpus (1)

• A Contextual-Bandit Approach to Personalized News Article Recommendation

Cited by in corpus (7)

• Policy Certificates: Towards Accountable Reinforcement Learning
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• PAC Reinforcement Learning with Rich Observations
• No-regret Exploration in Contextual Reinforcement Learning
• Markov Decision Processes with Continuous Side Information
• Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
• Continuous Control with Contexts, Provably