A Theoretical and Empirical Analysis of Expected Sarsa

H. Seijen; H.P. van Hasselt; S. Whiteson; M.A. Wiering

A Theoretical and Empirical Analysis of Expected Sarsa

H. Seijen, H.P. van Hasselt, S. Whiteson, M.A. Wiering

extern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

This paper presents a theoretical and empirical analysis of Expected Sarsa, a variation on Sarsa, the classic on-policy temporal-difference method for model-free reinforcement learning. Expected Sarsa exploits knowledge about stochasticity in the behavior policy to perform updates with lower variance. Doing so allows for higher learning rates and thus faster learning. In deterministic environments, Expected Sarsa's updates have zero variance, enabling a learning rate of 1. We prove that Expected Sarsa converges under the same conditions as Sarsa and formulate specific hypotheses about when Expected Sarsa will outperform Sarsa and Q-learning. Experiments in multiple domains confirm these hypotheses and demonstrate that Expected Sarsa has significant advantages over these more commonly used methods.

Original language	Undefined/Unknown
Title of host publication	Proceedings of the IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADRPL 2009)
Publisher	IEEE
Pages	177-184
Number of pages	8
Publication status	Published - 30 Mar 2009

Keywords

Wiskunde en Informatica (WIIN)

Access to Document

http://staff.science.uva.nl/~whiteson/pubs/b2hd-vanseijenadprl09.html

Cite this

@inproceedings{2bf4324c27b24cca8e8cca7e0f754e6b,

title = "A Theoretical and Empirical Analysis of Expected Sarsa",

abstract = "This paper presents a theoretical and empirical analysis of Expected Sarsa, a variation on Sarsa, the classic on-policy temporal-difference method for model-free reinforcement learning. Expected Sarsa exploits knowledge about stochasticity in the behavior policy to perform updates with lower variance. Doing so allows for higher learning rates and thus faster learning. In deterministic environments, Expected Sarsa's updates have zero variance, enabling a learning rate of 1. We prove that Expected Sarsa converges under the same conditions as Sarsa and formulate specific hypotheses about when Expected Sarsa will outperform Sarsa and Q-learning. Experiments in multiple domains confirm these hypotheses and demonstrate that Expected Sarsa has significant advantages over these more commonly used methods.",

keywords = "Wiskunde en Informatica (WIIN)",

author = "H. Seijen and {van Hasselt}, H.P. and S. Whiteson and M.A. Wiering",

note = "IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADRPL 2009)",

year = "2009",

month = mar,

day = "30",

language = "Undefined/Unknown",

pages = "177--184",

booktitle = "Proceedings of the IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADRPL 2009)",

publisher = "IEEE",

address = "United States",

}

TY - GEN

T1 - A Theoretical and Empirical Analysis of Expected Sarsa

AU - Seijen, H.

AU - van Hasselt, H.P.

AU - Whiteson, S.

AU - Wiering, M.A.

N1 - IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADRPL 2009)

PY - 2009/3/30

Y1 - 2009/3/30

N2 - This paper presents a theoretical and empirical analysis of Expected Sarsa, a variation on Sarsa, the classic on-policy temporal-difference method for model-free reinforcement learning. Expected Sarsa exploits knowledge about stochasticity in the behavior policy to perform updates with lower variance. Doing so allows for higher learning rates and thus faster learning. In deterministic environments, Expected Sarsa's updates have zero variance, enabling a learning rate of 1. We prove that Expected Sarsa converges under the same conditions as Sarsa and formulate specific hypotheses about when Expected Sarsa will outperform Sarsa and Q-learning. Experiments in multiple domains confirm these hypotheses and demonstrate that Expected Sarsa has significant advantages over these more commonly used methods.

AB - This paper presents a theoretical and empirical analysis of Expected Sarsa, a variation on Sarsa, the classic on-policy temporal-difference method for model-free reinforcement learning. Expected Sarsa exploits knowledge about stochasticity in the behavior policy to perform updates with lower variance. Doing so allows for higher learning rates and thus faster learning. In deterministic environments, Expected Sarsa's updates have zero variance, enabling a learning rate of 1. We prove that Expected Sarsa converges under the same conditions as Sarsa and formulate specific hypotheses about when Expected Sarsa will outperform Sarsa and Q-learning. Experiments in multiple domains confirm these hypotheses and demonstrate that Expected Sarsa has significant advantages over these more commonly used methods.

KW - Wiskunde en Informatica (WIIN)

M3 - Conference contribution

SP - 177

EP - 184

BT - Proceedings of the IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADRPL 2009)

PB - IEEE

ER -