On Lower Bounds for Regret in Reinforcement Learning

Abstract

This is a brief technical note to clarify the state of lower bounds on regret for reinforcement learning. In particular, this paper: - Reproduces a lower bound on regret for reinforcement learning, similar to the result of Theorem 5 in the journal UCRL2 paper (Jaksch et al 2010). - Clarifies that the proposed proof of Theorem 6 in the REGAL paper (Bartlett and Tewari 2009) does not hold using the standard techniques without further work. We suggest that this result should instead be considered a conjecture as it has no rigorous proof. - Suggests that the conjectured lower bound given by (Bartlett and Tewari 2009) is incorrect and, in fact, it is possible to improve the scaling of the upper bound to match the weaker lower bounds presented in this paper. We hope that this note serves to clarify existing results in the field of reinforcement learning and provides interesting motivation for future work.

Cited by in corpus (37)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Exploration in Structured Reinforcement Learning
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Variance Reduction Methods for Sublinear Reinforcement Learning
• $Q$-learning with Logarithmic Regret
• Near-Optimal Reinforcement Learning with Self-Play
• Learning to Control in Metric Space with Optimal Regret
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
• Making Sense of Reinforcement Learning and Probabilistic Inference
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• Robust Policy Gradient against Strong Data Corruption
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Adaptive Discretization for Model-Based Reinforcement Learning
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• No-regret Exploration in Contextual Reinforcement Learning
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Influence-Based Multi-Agent Exploration
• No-Regret Reinforcement Learning with Heavy-Tailed Rewards
• Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments
• On the Theory of Reinforcement Learning with Once-per-Episode Feedback
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• Reinforcement Learning with Feedback Graphs
• Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
• Accelerating the Computation of UCB and Related Indices for Reinforcement Learning
• Gap-Dependent Bounds for Two-Player Markov Games