Timezone: »

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

Tue Dec 10 05:15 PM -- 05:20 PM (PST) @ West Ballroom A + B

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.

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