Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes
Not on the map. Why?
Abstract (arXiv)
We study regret minimization for reinforcement learning (RL) in Latent Markov Decision Processes (LMDPs) with context in hindsight. We design a novel model-based algorithmic framework which can be instantiated with both a model-optimistic and a value-optimistic solver. We prove an tildeO(√mathsfVar^star M Gamma S A K) regret bound where tildeO hides logarithm factors, M is the number of contexts, S is the number of states, A is the number of actions, K is the number of episodes, Gamma ≤ S is the maximum transition degree of any state-action pair, and mathsfVar^star is a variance quantity describing the determinism of the LMDP. The regret bound only scales logarithmically with the planning horizon, thus yielding the first (nearly) horizon-free regret bound for LMDP. This is also the first problem-dependent regret bound for LMDP. Key in our proof is an analysis of the total variance of alpha vectors (a generalization of value functions), which is handled with a truncation method. We complement our positive result with a novel Omega(√mathsfVar^star M S A K) regret lower bound with Gamma = 2, which shows our upper bound minimax optimal when Gamma is a constant for the class of variance-bounded LMDPs. Our lower bound relies on new constructions of hard instances and an argument inspired by the symmetrization technique from theoretical computer science, both of which are technically different from existing lower bound proof for MDPs, and thus can be of independent interest.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 36 of its 58 references that are in the map. First posted on arXiv 20 Oct 2022.
Builds on
36 of 58 references.
References · 36
- 2019Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learningcited by 1,168
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2018Probabilistic Model-Agnostic Meta-Learningcited by 254
- 2015Contextual Markov Decision Processescited by 213
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
- 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
- 2020Reward-Free Exploration for Reinforcement Learningcited by 177
- 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
- 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
- 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
- 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
24 more
- 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
- 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
- 2013Hidden Parameter Markov Decision Processes: A Semiparametric Regression Approach for Discovering Latent Task Parametrizationscited by 68
- 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
- 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
- 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
- 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
- 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
- 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
- 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
- 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
- 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
- 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
- 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
- 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
- 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
- 2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
- 2020Meta-Learning with Shared Amortized Variational Inferencecited by 14
- 2019The Communication Complexity of Optimizationcited by 9
- 2022Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimizationcited by 2
- 2017On The Multiparty Communication Complexity of Testing Triangle-Freenesscited by 1
Built on by
Citing papers per year: 2024: 3.
3 papers.