The Role of Lookahead in Reinforcement Learning Algorithms

Winnicki, Anna

Permalink

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

Description

Title

The Role of Lookahead in Reinforcement Learning Algorithms

Author(s)

Winnicki, Anna

Issue Date

2024-04-26

Director of Research (if dissertation) or Advisor (if thesis)

Srikant, R.

Doctoral Committee Chair(s)

Srikant, R.

Committee Member(s)

• Hajek, Bruce
• Wierman, Adam
• Beck, Carolyn
• Sowers, Richard

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Reinforcement learning
• Markov Decision Processes

Abstract

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].

Graduation Semester

2024-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2024 Anna Winnicki

Owning Collections