The Role of Lookahead in Reinforcement Learning Algorithms

State of the art reinforcement learning (RL) algorithms such as AlphaZero use lookahead, which is typically implemented using Monte Carlo Tree Search (MCTS). As the name suggests, lookahead simply means looking ahead several steps when computing the policy to be used. The fact that an H-step lookahead provides an O(alpha^H), where alpha is the discount factor, approximate solution to the optimal policy is a somewhat trivial and well-known statement. What we have shown is a much stronger result: we have shown that lookahead leads to convergent learning algorithms while the same algorithms may diverge in the absence of lookahead. We have demonstrated these results for three different classes of RL algorithms: modified policy iteration with linear value function approximation [1], Monte Carlo with exploring starts [2], and policy iteration for zero-sum Markov games [3]. We have also shown that lookahead can be efficiently implemented in the widely studied class of linear MDPs [3].

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Winnicki, Anna

Contributors dc:contributor

• Srikant, R.
• Hajek, Bruce
• Wierman, Adam
• Beck, Carolyn
• Sowers, Richard

• Reinforcement Learning
• Markov Decision Processes

Statement dc:rights

• Copyright 2024 Anna Winnicki

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/124419

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F124419