No-regret Exploration in Contextual Reinforcement Learning
arXiv:1903.06187
Abstract
We consider the recently proposed reinforcement learning (RL) framework of Contextual Markov Decision Processes (CMDP), where the agent interacts with a (potentially adversarial) sequence of episodic tabular MDPs. In addition, a context vector determining the MDP parameters is available to the agent at the start of each episode, thereby allowing it to learn a context-dependent near-optimal policy. In this paper, we propose a no-regret online RL algorithm in the setting where the MDP parameters are obtained from the context using generalized linear mappings (GLMs). We propose and analyze optimistic and randomized exploration methods which make (time and space) efficient online updates. The GLM based model subsumes previous work in this area and also improves previous known bounds in the special case where the contextual mapping is linear. In addition, we demonstrate a generic template to derive confidence sets using an online learning oracle and give a lower bound for the setting.
arXiv commentAccepted to UAI 2020. PMLR proceedings, volume 124
References in corpus (7)
- (More) Efficient Reinforcement Learning via Posterior Sampling
- Provably Efficient Reinforcement Learning with Linear Function Approximation
- Provably Optimal Algorithms for Generalized Linear Contextual Bandits
- On Lower Bounds for Regret in Reinforcement Learning
- Online Stochastic Linear Optimization under One-bit Feedback
- Logistic Regression: The Importance of Being Improper
- Online learning in MDPs with side information
Cited by in corpus (4)
- Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
- Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
- Continuous Control with Contexts, Provably
- PAC Bounds for Imitation and Model-based Batch Learning of Contextual Markov Decision Processes