Improved worst-case regret bounds for randomized least-squares value iteration

This work studies regret minimization with randomized value functions in reinforcement learning. In tabular finite-horizon Markov Decision Processes, we introduce a clipping variant of one classical Thompson Sampling (TS)-like algorithm, randomized least-squares value iteration (RLSVI). Our \tilde{O}(H²S\sqrt{AT}) high-probability worst-case regret bound improves the previous sharpest worst-case regret bounds for RLSVI and matches the existing state-of-the-art worst-case TS-based regret bounds.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Agrawal, Priyank

Contributors dc:contributor

• Jiang, Nan

• Reinforcement Learning
• Exploration-Exploitation

Statement dc:rights

• Copyright 2021 Priyank Agrawal

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/113048

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/113048