Regret Bounds for Reinforcement Learning via Markov Chain Concentration

Ronald Ortner

doi:10.1613/jair.1.11316

Regret Bounds for Reinforcement Learning via Markov Chain Concentration

Ronald Ortner

Lehrstuhl für Informationstechnologie (150)

Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Begutachtung

3 Zitate (Scopus)

Abstract

We give a simple optimistic algorithm for which it is easy to derive regret bounds of Õ(√t _mixSAT) after T steps in uniformly ergodic Markov decision processes with S states, A actions, and mixing time parameter t _mix. These bounds are the first regret bounds in the general, non-episodic setting with an optimal dependence on all given parameters. They could only be improved by using an alternative mixing time parameter.

Originalsprache	Englisch
Seiten (von - bis)	115-128
Seitenumfang	14
Fachzeitschrift	The journal of artificial intelligence research
Jahrgang	67.2020
Ausgabenummer	1
DOIs	https://doi.org/10.1613/jair.1.11316
Publikationsstatus	Veröffentlicht - 23 Jan. 2020

Bibliographische Notiz

Funding Information:
This work has been supported by the Austrian Science Fund (FWF): I 3437-N33 in the framework of the CHIST-ERA ERA-NET (DELTA project). The author would like to thank Ronan Fruit, Alessandro Lazaric, and Matteo Pirotta for discussion as well as Sadegh Talebi, Chen-Yu Wei, and three anonymous reviewers for pointing out errors in a previous version of the paper.

Publisher Copyright:
© 2020 AI Access Foundation. All rights reserved.

Zugriff auf Dokument

10.1613/jair.1.11316

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Regret Bounds for Reinforcement Learning via Markov Chain Concentration
Ortner, R., 26 Aug. 2021.
Publikation: Konferenzbeitrag › Poster › Forschung › Begutachtung

Regret Bounds for Reinforcement Learning via Markov Chain Concentration
Ortner, R. (Redner)
26 Aug. 2021
Aktivität: Gespräch oder Vortrag › Mündliche Präsentation

Dieses zitieren

@article{f61ee437511b4018b0247bd02b96db23,

title = "Regret Bounds for Reinforcement Learning via Markov Chain Concentration",

abstract = "We give a simple optimistic algorithm for which it is easy to derive regret bounds of {\~O}(√t mixSAT) after T steps in uniformly ergodic Markov decision processes with S states, A actions, and mixing time parameter t mix. These bounds are the first regret bounds in the general, non-episodic setting with an optimal dependence on all given parameters. They could only be improved by using an alternative mixing time parameter. ",

author = "Ronald Ortner",

year = "2020",

month = jan,

day = "23",

doi = "10.1613/jair.1.11316",

language = "English",

volume = "67.2020",

pages = "115--128",

journal = " The journal of artificial intelligence research",

issn = "1076-9757",

publisher = "AI Access Foundation",

number = "1",

}

TY - JOUR

T1 - Regret Bounds for Reinforcement Learning via Markov Chain Concentration

AU - Ortner, Ronald

PY - 2020/1/23

Y1 - 2020/1/23

N2 - We give a simple optimistic algorithm for which it is easy to derive regret bounds of Õ(√t mixSAT) after T steps in uniformly ergodic Markov decision processes with S states, A actions, and mixing time parameter t mix. These bounds are the first regret bounds in the general, non-episodic setting with an optimal dependence on all given parameters. They could only be improved by using an alternative mixing time parameter.

AB - We give a simple optimistic algorithm for which it is easy to derive regret bounds of Õ(√t mixSAT) after T steps in uniformly ergodic Markov decision processes with S states, A actions, and mixing time parameter t mix. These bounds are the first regret bounds in the general, non-episodic setting with an optimal dependence on all given parameters. They could only be improved by using an alternative mixing time parameter.

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

U2 - 10.1613/jair.1.11316

DO - 10.1613/jair.1.11316

M3 - Article

SN - 1076-9757

VL - 67.2020

SP - 115

EP - 128

JO - The journal of artificial intelligence research

JF - The journal of artificial intelligence research

IS - 1

ER -

Regret Bounds for Reinforcement Learning via Markov Chain Concentration

Abstract

Bibliographische Notiz

Zugriff auf Dokument

Andere Dateien und Links

Publikationen