Near-Minimax-Optimal Risk-Sensitive RL with CVaR
24. července 2023
Řečníci
Kaiwen Wang
Řečník · 0 sledujících
Nathan Kallus
Řečník · 2 sledující
O prezentaci
In this paper, we study risk-sensitive Reinforcement Learning (RL), focusing on the objective of Conditional Value at Risk (CVaR) with risk tolerance τ. Starting with multi-arm bandits (MABs), we show the minimax CVaR regret rate is Ω(√(τ^-1AK)), where A is the number of actions and K is the number of episodes, and that it is achieved by an Upper Confidence Bound algorithm with a novel Bernstein bonus. For online RL in tabular Markov Decision Processes (MDPs), we show a minimax regret lower bound of Ω(√(τ^-1SAK)) (with normalized cumulative rewards), where S is the number of states, and we propose a novel bonus-driven Value Iteration procedure. We show that our algorithm achieves the optimal regret of O(√(τ^-1SAK)) under a continuity assumption and in general attains a near-optimal regret of O(τ^-1√(SAK)), which is minimax-optimal for constant τ. This improves on the best available bounds. By discretizing rewards appropriately, our algorithms are computationally efficient.In this paper, we study risk-sensitive Reinforcement Learning (RL), focusing on the objective of Conditional Value at Risk (CVaR) with risk tolerance τ. Starting with multi-arm bandits (MABs), we show the minimax CVaR regret rate is Ω(√(τ^-1AK)), where A is the number of actions and K is the number of episodes, and that it is achieved by an Upper Confidence Bound algorithm with a novel Bernstein bonus. For online RL in tabular Markov Decision Processes (MDPs), we show a minimax regret lower boun…
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Extrapolated Random Tree for Regression
Zhlédnout později
Yuchao Cai, …
Adapting to game trees in zero-sum imperfect information games
Zhlédnout později
Côme Fiegel, …
On the Relationship Between Explanation and Prediction: A Causal View
Zhlédnout později
Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes
Zhlédnout později
Continuation Path Learning for Homotopy Optimization
Zhlédnout později
Xi Lin, …
Learning Preconditioner for Conjugate Gradient PDE Solver
Zhlédnout později
Yichen Li, …