PaperlayerView exact revision on arXiv

Source-linked AI summary

Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes

Chen-Yu Wei, Mehdi Jafarnia-Jahromi, Haipeng Luo, Hiteshi Sharma, Rahul Jain

arXiv:1910.07072v2cs.LGcs.AIstat.ML

TL;DR

Low-regret model-free learning for infinite-horizon average-reward MDPs remained unresolved, with unbounded Q-value estimates creating a challenge. The paper introduces discounted-reduction and policy-optimization algorithms, obtaining improved regret bounds under weakly communicating and ergodic assumptions. The ergodic algorithm's bound also depends on mixing time.

  • Problem

    Low-regret Q-learning for infinite-horizon average-reward MDPs remained unknown, with Q-value estimates potentially growing unbounded and standard finite-horizon or discounted techniques unavailable.

    Source: §1 · p. 1

  • Method

    The paper proposes Optimistic Q-learning, which introduces a discount factor, and MDP-OOMD, which uses per-state bandit learning with adaptive adversarial-bandit methods.

    Source: §1 · p. 2

  • Results

    Optimistic Q-learning achieves eO(T^2/3) regret for weakly communicating MDPs; MDP-OOMD attains eO(T) for ergodic MDPs, improving on POLITEX's eO(T^3/4).

    Source: §1 · p. 2

  • Takeaways & Limitations

    Achieving the information-theoretically optimal regret bound with a model-free algorithm remains an open question.

    Source: §6 · p. 9

    MDP-OOMD is restricted to ergodic MDPs, and its bound has an extra dependence on mixing time, a potentially large constant.

    Source: §1 · p. 2, §5.1 · p. 7

Abstract

from arXiv · show

Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-reward Markov Decision Processes (MDPs). The first algorithm reduces the problem to the discounted-reward version and achieves $\mathcal{O}(T^{2/3})$ regret after $T$ steps, under the minimal assumption of weakly communicating MDPs. To our knowledge, this is the first model-free algorithm for general MDPs in this setting. The second algorithm makes use of recent advances in adaptive algorithms for adversarial multi-armed bandits and improves the regret to $\mathcal{O}(\sqrt{T})$, albeit with a stronger ergodic assumption. This result significantly improves over the $\mathcal{O}(T^{3/4})$ regret achieved by the only existing model-free algorithm by Abbasi-Yadkori et al. (2019a) for ergodic MDPs in the infinite-horizon average-reward setting.

1. Introduction

The introduction motivates model-free learning for infinite-horizon average-reward MDPs by its efficiency, while noting that low-regret methods in this setting were missing. It presents two algorithms with different assumptions and approaches.

1. Introduction

  • Model-free algorithms maintain estimates of the optimal Q-function or policy and are described as computation- and memory-efficient and easier to extend to large-scale problems.Model-based methods require memory for model estimates and are difficult to extend to non-parametric settings such as continuous-state MDPs.Source: §1 · p. 1
  • Low-regret Q-learning for infinite-horizon average-reward MDPs remained unresolved, in part because Q estimates may grow unbounded and standard finite-horizon or discounted techniques do not apply.The paper also reports experiments comparing its two algorithms, with details deferred to Appendix D.Source: §1 · pp. 1–2
  • Optimistic Q-learning achieves eO(T^2/3) regret for weakly communicating MDPs, while MDP-OOMD attains eO(T) for ergodic MDPs, improving on POLITEX's eO(T^3/4) bound.The first algorithm removes the ergodicity assumption; the second uses a stronger ergodic assumption.Source: §1 · p. 2
  • Optimistic Q-learning introduces a discount factor to control unbounded Q-value estimates, balancing that effect against the approximation to the undiscounted problem.The paper distinguishes this approach from R-learning, which uses no discount factor.Source: §1 · p. 2
  • MDP-OOMD maintains a multi-armed bandit algorithm at each state and uses adaptive adversarial-bandit advances to learn actions.The paper says the bandit algorithm must satisfy key properties for the claimed regret bound.Source: §1 · p. 2

2. Related Work

Prior work established near-optimal guarantees in finite-horizon and discounted settings, but average-reward methods faced trade-offs in regret, computational efficiency, and model-free generality.

2. Related Work

  • For finite-horizon and discounted MDPs, prior work achieved nearly information-theoretically optimal regret or sample complexity using model-based and model-free approaches.The cited examples include model-based methods and Q-learning-based methods.Source: §2 · p. 2
  • Average-reward model-based algorithms achieved eO(T) regret, but some approaches had suboptimal parameter dependence, while methods toward optimal bounds could scale exponentially in the number of states.The review also describes POLITEX as the only existing model-free algorithm for the setting apart from naive Q-learning with epsilon-greedy exploration.Source: §2 · p. 3
  • Among model-free algorithms for this setting, aside from naive Q-learning with ε-greedy exploration, POLITEX is the only existing one, and it only works for ergodic MDPs.POLITEX is also studied in a more general setup with function approximation.Source: §2 · pp. 2–3
  • Neu et al. (2013) and Wang (2017) also use policy optimization, but their settings differ and their results are not comparable to MDP-OOMD.The paper defers detailed comparisons to the end of Section 5.1.Source: §2 · p. 3

3. Preliminaries

The preliminaries define the finite-state, finite-action average-reward MDP and learning setup, then specify regret and the MDP classes considered.

3. Preliminaries

  • The MDP has finite state and action sets, reward function r, and transition probabilities p; policies are evaluated by average reward per stage.The optimal policy maximizes the optimal average reward from every state.Source: §3 · p. 3
  • The paper studies weakly communicating and ergodic MDPs, with weak communication described as the weaker assumption.The text identifies weak communication as necessary for low-regret learning of infinite-horizon MDPs.Source: §3 · p. 3
  • The learner knows the state and action spaces and reward function but not the transition probabilities, and begins from an arbitrary state.At each step, the learner observes the state, chooses an action from its history, and receives the next state through the unknown transition kernel.Source: §3 · p. 3
  • Regret is the cumulative reward gap between the optimal policy and the learning algorithm; sublinear regret makes average reward converge to the optimal per-stage reward.The cited best existing bound is eO(DSAT) for a model-based algorithm, matching the stated lower bound.Source: §3 · p. 3

4. Optimistic Q-Learning

This section presents methods for average-reward learning, including optimistic Q-learning and MDP-OOMD, and sketches the OOMD regret analysis. It also compares POLITEX with the paper’s method and develops auxiliary results for that analysis.

4. Optimistic Q-Learning

  • The algorithm solves the undiscounted problem by learning a discounted MDP, choosing greedy actions and updating Q estimates with a visit-count-dependent exploration bonus and step size.The bonus scales as O(sqrt(H/τ)) and shrinks with each visit to a state-action pair.Source: §4 · p. 4

4.1. Proof sketch of Theorem 1

  • The regret analysis addresses discounted-to-undiscounted approximation and improves on Dong et al. (2019), with the discounted optimal value-function span bounded by twice the undiscounted span.This is distinct from Dong et al. (2019), whose analysis concerned sample complexity rather than regret.Source: §4 · p. 4, §4.1 · p. 5

5.1. Policy Optimization via Optimistic OMD

  • For ergodic MDPs, MDP-OOMD learns the optimal policy by running an independent adversarial bandit algorithm at each state and updating policies across episodes.Its reward estimator averages estimates from spaced, non-overlapping trajectory intervals to reduce variance.Source: §5.1 · pp. 6–7
  • OOMD with a log-barrier regularizer avoids explicit action exploration, stabilizes updates, and combines optimistic predictions with the estimator to reduce variance and obtain a bound in terms of ρ rather than thit.The guarantee still depends on tmix, which the analysis uses to control trajectory length and the magnitude of Q- and value-functions.Source: §5.1 · p. 7
  • Abbasi-Yadkori et al. (2019a)’s POLITEX has regret significantly worse than the paper’s method in all parameters.The passage introduces POLITEX as a function-approximation algorithm that maintains a standard exponential-weight algorithm for each state.Source: §5.1 · p. 8

5.2. Proof sketch of Theorem 5

  • The proof sketch decomposes regret, bounds one term using state-wise multi-armed-bandit regret, and bounds another by O(ηN^3K) and O(tmix).The latter bounds come respectively from OOMDUPDATE stability and Lemma 14; the proof then combines terms with N = eO(tmix) and B = eO(tmixthit) and chooses η optimally.Source: §5.2 · p. 8

5.3. Auxiliary Lemmas

  • The auxiliary lemmas establish that bβk(s, a) is almost unbiased for βπk(s, a) and that consecutive policies’ β values differ by at most O(ηN^3).The section also states an OOMD regret bound for a specific state, analyzed similarly to Wei & Luo (2018).Source: §5.3 · pp. 8–9

6. Conclusions

The paper presents two model-free approaches to infinite-horizon average-reward MDPs, using different strategies. Whether model-free methods can achieve the information-theoretically optimal regret bound remains open.

6. Conclusions

  • The paper proposes two model-free algorithms for infinite-horizon average-reward MDPs.One reduces the problem to the discounted setting; the other directly optimizes the policy using adaptive adversarial multi-armed bandit algorithms.Source: §6 · p. 9
  • Whether a model-free algorithm can achieve the information-theoretically optimal regret bound remains an open question.The authors suggest their techniques may help answer it.Source: §6 · p. 9
  • The two algorithms are based on different ideas: discounted-problem reduction and direct policy optimization.Source: §6 · p. 9

A. Omitted Proofs in Section 4

The omitted proofs rely on learning-rate properties and Azuma’s inequality. The supplied passages identify these tools but provide only limited detail about the resulting arguments.

A. Omitted Proofs in Section 4

A.1. Proof of Lemma 2

The proof compares optimal value functions in discounted and undiscounted settings. It establishes that the discounted optimal value function has at most twice the span of the undiscounted one.

A.1. Proof of Lemma 2

  • The discounted optimal value function satisfies sp(V*) ≤ 2 sp(v*).Source: §A.1 · pp. 12–13
  • The proof compares the optimal policies in the two settings using Bellman equations and their respective sub-optimality relations.It considers state sequences generated first by the undiscounted-optimal policy and then by the discounted-optimal policy.Source: §A.1 · pp. 12–13
  • The span comparison is restated as the conclusion of Lemma 2.Source: §A.1 · p. 13

A.2. Proof of Lemma 3

These appendices establish bounds used in the analysis, including a high-probability control for the Q-learning estimates and a state-visit bound under ergodicity. They also use Azuma’s inequality and a value-function span comparison in the proof of Lemma 4.

A.2. Proof of Lemma 3

  • With probability at least 1 − δ, Lemma 12 bounds the estimates for every timestep and state-action pair.The proof uses this bound alongside the non-increasing estimates, whose total decrease is at most H for each state-action pair.Source: §A.2 · pp. 13, 15

A.3. Proof of Lemma 4

  • For the proof of Lemma 4, Azuma’s inequality and sp(V*) ≤ 2 sp(v*) bound a martingale term; the remaining endpoint difference is also bounded using the span.Source: §A.3 · p. 16

B.1. Auxiliary Lemmas

  • For a period I of an Algorithm 2 episode with |I| ≥ N = 4 t_mix log^2 T, Lemma 16 upper-bounds the probability that the algorithm never visits a given state s in I.Source: §B.1 · p. 17

B.2. Proof for Lemma 6

ESTIMATEQ averages reward estimates from disjoint state-starting intervals, with rest periods intended to reduce dependence between collected rewards and the number of intervals. Its proof uses an imaginary process with stationary-distribution resets, then compares that process with the real one.

B.2. Proof for Lemma 6

  • In an imaginary process that resets to the stationary distribution after each rest, interval estimates are almost unbiased, and their average is expected to have small error.The proof treats the centered interval estimates as conditionally zero-mean and independent given the wait times.Source: §B.2 · pp. 18, 19, 22
  • Because the interval count M is random and dependent on the reward estimators, the estimator’s expectation requires a two-step argument rather than a direct independence claim.The argument first establishes near-unbiasedness in the imaginary process, then compares expectations across processes.Source: §B.2 · p. 19
  • ESTIMATEQ collects disjoint length-(N + 1) intervals starting at state s, records each interval’s reward, and averages the resulting estimates.After each interval, it waits N steps before seeking another visit to s.Source: §B.2 · p. 19, Figure 1 · p. 19
  • The N-step rest is intended to decorrelate observed rewards from the number of collected intervals by letting the process nearly forget earlier estimates.The argument relies on N being longer than the mixing time, so later wait-point distributions are close to the stationary distribution.Source: §B.2 · p. 19
  • The proof then compares real and imaginary trajectory probabilities, whose difference arises because the reset changes the distribution of the next interval’s start time.It uses this comparison to relate the estimator expectations in the two processes.Source: §B.2 · pp. 19–21

B.3. Proof for Lemma 7

This proof bounds changes in policy-value quantities across episodes and establishes the stability and regret properties used in the analysis of optimistic online mirror descent.

B.3. Proof for Lemma 7

  • The proof bounds changes in the value vector across successive policies, using transition-kernel differences and the stability relation in Eq. (13).It then derives a corresponding bound on changes in β using changes in q and average reward.Source: §B.3 · pp. 23–24
  • The analysis runs optimistic online mirror descent independently at each state, with the log-barrier regularizer providing the stability property used in the regret analysis.The section states that its analysis focuses on one state at a time.Source: §B.3 · p. 24
  • The proof verifies the update’s input condition from the interval reward estimates, whose total reward is bounded by the interval length N + 1.When no interval is collected, ESTIMATEQ sets the estimate to zero.Source: §B.3 · p. 24

C.1. The stability property of Algorithm 5 — Proof of Eq.(13)

The appendix establishes stability for the log-barrier OOMD update and uses that analysis to prove regret bounds for the algorithm.

C.1. The stability property of Algorithm 5 — Proof of Eq.(13)

  • Under the stated gradient-scaled difference condition, Lemma 18 bounds each updated probability’s change relative to its original coordinate by 60ηC.The lemma compares minimizers formed from two loss vectors under the same regularizer.Source: §C.1 · p. 25

C.2. The regret bound of Algorithm 5 — Proof of Lemma 8

  • The Lemma 8 proof applies standard optimistic online mirror descent analysis and bounds its estimator-dependent terms to complete the regret argument.The passage concludes by using E[bβk(s)] = O(N).Source: §C.2 · pp. 28–29

C.3. Proof for Lemma 9

  • The second, fourth, and third terms in (43) are bounded using Eq. (12), Lemma 17 (πk(a|s) ≤ 2πk−1(a|s)), and Lemma 7, respectively; the bounds are combined, multiplied by Bµ∗(s), and summed over s.Source: §C.3 · p. 30

D. Experiments

In experiments on a random MDP and JumpRiverSwim, the proposed algorithms achieve sublinear regret, while standard ε-greedy Q-learning has linear regret. Optimistic Q-learning performs best on JumpRiverSwim, whereas the proposed algorithms and POLITEX perform similarly on the random MDP.

D. Experiments

  • Both test environments have 6 states and 2 actions; JumpRiverSwim adds a 0.01 chance of moving to an arbitrary state at each step, making the environment ergodic.The random MDP’s reward function and transition kernel are chosen uniformly at random.Source: D. Experiments · p. 31
  • On JumpRiverSwim, Optimistic Q-learning outperforms the other three algorithms; on the random MDP, it, MDP-OOMD, and POLITEX have similar performance.The standard ε-greedy Q-learning algorithm suffers linear regret, while Optimistic Q-learning and MDP-OOMD achieve sublinear regret.Source: D. Experiments · p. 31, Figure 3 · p. 31
  • Experiments average 10 independent runs over a horizon of 5 × 10^6 steps, with hyperparameters optimized for each algorithm.Source: Table 2 · p. 32
Loading 1910.07072v2…