Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes
Jul 24, 2023
Speakers
Runlong Zhou
Speaker · 0 followers
Ruosong Wang
Speaker · 0 followers
Simon Shaolei Du
Speaker · 0 followers
About
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 Õ(√(𝖵𝖺𝗋^⋆ M Γ S A K)) regret bound where Õ 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, Γ< S is the maximum transition degree of any state-action pair, and 𝖵𝖺𝗋^⋆ 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 Ω(√(𝖵𝖺𝗋^⋆ M S A K)) regret lower bound with Γ = 2, which shows our upper bound minimax optimal when Γ 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.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 Õ(√(𝖵𝖺𝗋^⋆ M Γ S A K)) regret bound where Õ 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, Γ< S is the maximum transition…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching
Watch later
Xuanzhou Liu, …
Preprocessors Matter! Realistic Decision-Based Attacks on Machine Learning Systems
Watch later
Uncertain Evidence in Probabilistic Models and Stochastic Simulators
Watch later
Andreas Munk, …
Structure in Monge Maps by Engineering Costs
Watch later
The Benefits of Model-Based Generalization in Reinforcement Learning
Watch later
Kenny Young, …