# Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation

arXiv: https://arxiv.org/abs/2210.07338 · HTML: https://mlsanity.com/paper/2210.07338/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 13 Oct 2022.

## Builds on (most cited first, 7 of 7)

- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control](https://mlsanity.com/paper/2108.10315/) (2021)
- [The Dynamics of Gradient Descent for Overparametrized Neural Networks](https://mlsanity.com/paper/2105.06569/) (2021)
- [Distributed Reinforcement Learning via Gossip](https://mlsanity.com/paper/1310.7610/) (2013)
- [Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning](https://mlsanity.com/paper/1805.07956/) (2018)
- [Optimistic Policy Iteration for MDPs with Acyclic Transient State Structure](https://mlsanity.com/paper/2102.00030/) (2021)

## Built on by (most cited first, 4 of 4)

- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Multi-Bellman operator for convergence of Q-learning with linear function approximation](https://mlsanity.com/paper/2309.16819/) (2023)
- [A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games](https://mlsanity.com/paper/2303.09716/) (2023)
- [Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Cost](https://mlsanity.com/paper/2410.15156/) (2024)

## Abstract (arXiv)

We provide performance guarantees for a variant of simulation-based policy iteration for controlling Markov decision processes that involves the use of stochastic approximation algorithms along with state-of-the-art techniques that are useful for very large MDPs, including lookahead, function approximation, and gradient descent. Specifically, we analyze two algorithms; the first algorithm involves a least squares approach where a new set of weights associated with feature vectors is obtained via least squares minimization at each iteration and the second algorithm involves a two-time-scale stochastic approximation algorithm taking several steps of gradient descent towards the least squares solution before obtaining the next iterate using a stochastic approximation algorithm.