Timezone: »

 
Poster
Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
Yonathan Efroni · Nadav Merlis · Mohammad Ghavamzadeh · Shie Mannor

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #191
in Reinforcement Learning and Planning -- Model-Based RL »

State-of-the-art efficient model-based Reinforcement Learning (RL) algorithms typically act by iteratively solving empirical models, i.e., by performing full-planning on Markov Decision Processes (MDPs) built by the gathered experience. In this paper, we focus on model-based RL in the finite-state finite-horizon MDP setting and establish that exploring with greedy policies -- act by 1-step planning -- can achieve tight minimax performance in terms of regret, O(\sqrt{HSAT}). Thus, full-planning in model-based RL can be avoided altogether without any performance degradation, and, by doing so, the computational complexity decreases by a factor of S. The results are based on a novel analysis of real-time dynamic programming, then extended to model-based RL. Specifically, we generalize existing algorithms that perform full-planning to such that act by 1-step planning. For these generalizations, we prove regret bounds with the same rate as their full-planning counterparts.

Keywords: Reinforcement Learning and Planning -> Model-Based RL · Reinforcement Learning and Planning -> Exploration; Reinforcement Learning and Planning -> Planning

Author Information

Yonathan Efroni (Technion)
Nadav Merlis (Technion)
Mohammad Ghavamzadeh (Facebook AI Research)
Shie Mannor (Technion)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors