VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation

Alekh Agarwal; Yujia Jin; Tong Zhang

VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation

Alekh Agarwal
, Yujia Jin
, Tong Zhang

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

Abstract

We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic QLearning (VOQL), based on Q-learning and bound its regret assuming closure under Bellman backups, and bounded Eluder dimension for the regression function class. As a special case, VOQL achieves O^e(d√TH + d⁶H⁵) regret over T episodes for a horizon H MDP under (ddimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.

Original language	English
Title of host publication	Proceedings of Thirty Sixth Conference on Learning Theory
Publisher	ML Research Press
Pages	987-1063
Number of pages	77
Volume	195
Publication status	Published - 12 Jul 2023
Externally published	Yes
Event	36th Annual Conference on Learning Theory, COLT 2023 - Bangalore, India Duration: 12 Jul 2023 → 15 Jul 2023

Publication series

Name	Proceedings of Machine Learning Research
Publisher	ML Research Press
Volume	195
ISSN (Print)	2640-3498

Conference

Conference	36th Annual Conference on Learning Theory, COLT 2023
Country/Territory	India
City	Bangalore
Period	12/07/23 → 15/07/23

Bibliographical note

Publisher Copyright:
© 2023 A. Agarwal, Y. Jin & T. Zhang.

Keywords

Reinforcement learning
nonlinear function approximation
model-free algorithms
eluder dimension

Access to Document

https://proceedings.mlr.press/v195/agarwal23a.html

Cite this

@inproceedings{e3ef39a43ad44d5aa5d6ee492a936621,

title = "VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation",

abstract = "We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic QLearning (VOQL), based on Q-learning and bound its regret assuming closure under Bellman backups, and bounded Eluder dimension for the regression function class. As a special case, VOQL achieves Oe(d√TH + d6H5) regret over T episodes for a horizon H MDP under (ddimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.",

keywords = "Reinforcement learning, nonlinear function approximation, model-free algorithms, eluder dimension",

author = "Alekh Agarwal and Yujia Jin and Tong Zhang",

note = "Publisher Copyright: {\textcopyright} 2023 A. Agarwal, Y. Jin \& T. Zhang.; 36th Annual Conference on Learning Theory, COLT 2023 ; Conference date: 12-07-2023 Through 15-07-2023",

year = "2023",

month = jul,

day = "12",

language = "English",

volume = "195",

series = "Proceedings of Machine Learning Research",

publisher = "ML Research Press",

pages = "987--1063",

booktitle = "Proceedings of Thirty Sixth Conference on Learning Theory",

}

Agarwal, A, Jin, Y & Zhang, T 2023, VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation. in Proceedings of Thirty Sixth Conference on Learning Theory. vol. 195, Proceedings of Machine Learning Research, vol. 195, ML Research Press, pp. 987-1063, 36th Annual Conference on Learning Theory, COLT 2023, Bangalore, India, 12/07/23. <https://proceedings.mlr.press/v195/agarwal23a.html>

VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation. / Agarwal, Alekh; Jin, Yujia; Zhang, Tong.
Proceedings of Thirty Sixth Conference on Learning Theory. Vol. 195 ML Research Press, 2023. p. 987-1063 (Proceedings of Machine Learning Research; Vol. 195).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - VOQL

T2 - 36th Annual Conference on Learning Theory, COLT 2023

AU - Agarwal, Alekh

AU - Jin, Yujia

AU - Zhang, Tong

PY - 2023/7/12

Y1 - 2023/7/12

N2 - We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic QLearning (VOQL), based on Q-learning and bound its regret assuming closure under Bellman backups, and bounded Eluder dimension for the regression function class. As a special case, VOQL achieves Oe(d√TH + d6H5) regret over T episodes for a horizon H MDP under (ddimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.

AB - We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic QLearning (VOQL), based on Q-learning and bound its regret assuming closure under Bellman backups, and bounded Eluder dimension for the regression function class. As a special case, VOQL achieves Oe(d√TH + d6H5) regret over T episodes for a horizon H MDP under (ddimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.

KW - Reinforcement learning

KW - nonlinear function approximation

KW - model-free algorithms

KW - eluder dimension

UR - https://www.scopus.com/pages/publications/85171526206

M3 - Conference Paper published in a book

AN - SCOPUS:85171526206

VL - 195

T3 - Proceedings of Machine Learning Research

SP - 987

EP - 1063

BT - Proceedings of Thirty Sixth Conference on Learning Theory

PB - ML Research Press

Y2 - 12 July 2023 through 15 July 2023

ER -

VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this