Variational Regret Bounds for Reinforcement Learning
arXiv:1905.05857
Abstract
We consider undiscounted reinforcement learning in Markov decision processes (MDPs) where both the reward functions and the state-transition probabilities may vary (gradually or abruptly) over time. For this problem setting, we propose an algorithm and provide performance guarantees for the regret evaluated against the optimal non-stationary policy. The upper bound on the regret is given in terms of the total variation in the MDP. This is the first variational regret bound for the general reinforcement learning setting.
arXiv commentPresented at UAI 2019
References in corpus (2)
Cited by in corpus (16)
- Game-Theoretic Multiagent Reinforcement Learning
- Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
- Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning
- Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
- Nonstationary Reinforcement Learning with Linear Function Approximation
- Dynamic Regret of Policy Optimization in Non-stationary Environments
- Robust Policy Gradient against Strong Data Corruption
- A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
- Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
- Autonomous exploration for navigating in non-stationary CMPs
- Contextual Blocking Bandits
- Efficient Learning in Non-Stationary Linear Markov Decision Processes
- Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems
- Learning and Planning for Time-Varying MDPs Using Maximum Likelihood Estimation
- Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
- Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty