Regret Bounds for Reinforcement Learning via Markov Chain Concentration

By Ronald Ortner. 2018

50 citations recorded by the source corpus.

We give a simple optimistic algorithm for which it is easy to derive regret bounds of O(sqrt{t-mix SAT}) 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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Jonathan Lee
2. Aldo Pacchiano
3. Aadirupa Saha

In Management Science and Operations Research

1. Jonathan Lee
2. Aldo Pacchiano
3. Aadirupa Saha

In Reinforcement Learning

1. Jonathan Lee
2. Aldo Pacchiano
3. Aadirupa Saha

Citations in the corpus

• Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “, 2020a; Lattimore and Hutter, 2012) and minimizing regret via balancing exploration and exploitation (Zhang and Ji, 2019; Azar et al., 2017; Ortner, 2020; Talebi and Maillard, 2018; Efroni et al., 2020; Domingues et al., 2020b).”