Online learning in MDPs with side information
This work addresses episodic decision-making problems like clinical trials and recommendation systems, providing a novel algorithm for competing with optimal dynamic policies.
The paper tackles online learning in Markov decision processes with side information, achieving a regret bound of O(√T) for the first time in this setting.
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.