Near-Optimal Randomized Exploration for Tabular Markov Decision Processes
Nov 28, 2022
Speakers
Zhihan Xiong
Speaker · 0 followers
Ruoqi Shen
Speaker · 0 followers
Maryam Fazel
Speaker · 0 followers
Simon S. Du
Speaker · 3 followers
About
We study algorithms using randomized value functions for exploration in reinforcement learning. This type of algorithms enjoys appealing empirical performance. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case O(H√(SAT)) regret bound for episodic time-inhomogeneous Markov Decision Process where S is the size of state space, A is the size of action space, H is the planning horizon and T is the number of interactions. This bound polynomially improves all existing bounds for algorithms based on randomized value functions, and for the first time, matches the Ω(H√(SAT)) lower bound up to logarithmic factors. Our result highlights that randomized exploration can be near-optimal, which was previously achieved only by optimistic algorithms. To achieve the desired result, we develop 1) a new clipping operation to ensure both the probability of being optimistic and the probability of being pessimistic are lower bounded by a constant, and 2) a new recursive formula for the absolute value of estimation errors to analyze the regret.We study algorithms using randomized value functions for exploration in reinforcement learning. This type of algorithms enjoys appealing empirical performance. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case O(H√(SAT)) regret bound for episodic time-inhomogeneous Markov Decision Process where S is the size of state space, A is the size of action space, H is the planning horizon and T is the number of interaction…
Organizer
NeurIPS 2022
Account · 953 followers
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
Score-based Generative Models and Their Applications
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Cross-Linked Unified Embedding for cross-modality representation learning
Watch later
Xinming Tu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Maximum a posteriori natural scene reconstruction from retinal ganglion cells with deep denoiser priors
Watch later
Eric G. Wu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
HyperMiner: Topic Taxonomy Mining with Hyperbolic Embedding
Watch later
Yishi Xu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Approximate Value Equivalence
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Leveraging Maths to Understand Transformers
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%