Text

Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds

We present an algorithm based on posterior sampling (aka Thompson sampling) that achieves near-optimal worst-case regret bounds when the underlying Markov decision process (MDP) is communicating with a finite, although unknown, diameter. Our main result is a high probability regret upper bound of O˜(DSAT−−−√) for any communicating MDP with S states, A actions, and diameter D. Here, regret compares the total reward achieved by the algorithm to the total expected reward of an optimal infinite-horizon undiscounted average reward policy in time horizon T. This result closely matches the known lower bound of Ω(DSAT−−−−−√). Our techniques involve proving some novel results about the anti-concentration of Dirichlet distribution, which may be of independent interest.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.48 No.1 February 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 363-392

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

MARKOV DECISION PROCESS
REGRET BOUNDS
REINFORCEMENT LEARNING
THOMPSON SAMPLING

Info Detail Spesifik

https://doi.org/10.1287/moor.2022.1266

Pernyataan Tanggungjawab

Shipra Agrawal, Randy Jia

Versi lain/terkait

Lampiran Berkas

Komentar