PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Unknown Markov Decision Processes: A Thompson Sampling Approach

Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, Rahul Jain

arXiv:1709.04570v1cs.LG

TL;DR

Learning an unknown infinite-horizon MDP requires balancing cost-minimizing actions with exploration of uncertain dynamics. TSDE samples a posterior model and follows its optimal stationary policy within dynamically ended episodes. The paper establishes a regret bound matching the best available order for weakly communicating MDPs and reports that TSDE outperforms other infinite-horizon learning algorithms numerically.

  • Problem

    In infinite-horizon MDPs, an agent must minimize cumulative cost while learning unknown dynamics, and certainty-equivalent estimation may underperform because it lacks exploration.

    Source: §1 · p. 1

  • Method

    TSDE samples transition parameters from the posterior at each episode’s start, follows the sampled model’s optimal stationary policy, and uses two criteria to end episodes dynamically.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    TSDE’s expected regret bound matches the best available order for weakly communicating MDPs, and numerical results show it outperforms other learning algorithms for infinite-horizon MDPs.

    Source: §1 · p. 2, §3.1 · p. 4, §6 · p. 8

  • Takeaways & Limitations

    The result fills a gap in the theoretical analysis of Thompson Sampling for MDPs, while simulations support TSDE’s performance against other infinite-horizon algorithms.

    Source: §6 · p. 8

    The guarantee is scoped to weakly communicating MDPs with span at most H, as imposed on the prior’s support.

    Source: §2.1 · p. 2, §2.2 · p. 3

Abstract

from arXiv · show

We consider the problem of learning an unknown Markov Decision Process (MDP) that is weakly communicating in the infinite horizon setting. We propose a Thompson Sampling-based reinforcement learning algorithm with dynamic episodes (TSDE). At the beginning of each episode, the algorithm generates a sample from the posterior distribution over the unknown model parameters. It then follows the optimal stationary policy for the sampled model for the rest of the episode. The duration of each episode is dynamically determined by two stopping criteria. The first stopping criterion controls the growth rate of episode length. The second stopping criterion happens when the number of visits to any state-action pair is doubled. We establish $\tilde O(HS\sqrt{AT})$ bounds on expected regret under a Bayesian setting, where $S$ and $A$ are the sizes of the state and action spaces, $T$ is time, and $H$ is the bound of the span. This regret bound matches the best available bound for weakly communicating MDPs. Numerical results show it to perform better than existing algorithms for infinite horizon MDPs.

1 Introduction

In infinite-horizon MDP learning, uncertainty about transition dynamics creates an exploration–exploitation trade-off that certainty-equivalent estimates may handle poorly. The paper proposes TSDE for weakly communicating MDPs and reports regret guarantees and stronger numerical performance than existing algorithms.

1 Introduction

  • Certainty equivalence estimates unknown MDP parameters and acts as if those estimates were true, but may perform suboptimally because it lacks exploration.The broader challenge is balancing cost-minimizing exploitation with exploration to learn the dynamics.Source: §1 · p. 1
  • Thompson Sampling samples unknown MDP parameters from a posterior and chooses actions using the sampled model during an episode; it can incorporate prior structure and solve only one sampled MDP per episode.The passage also reports empirical advantages over optimistic methods in bandit problems and MDPs.Source: §1 · p. 2
  • Existing Thompson Sampling episode schedules did not cover MDPs lacking special recurrent-state or finite-horizon structure, leaving strong guarantees for general MDPs unresolved after a proof error was identified in [20].The cited proof error was pointed out by [20].Source: §1 · p. 2
  • TSDE samples a model from the posterior at each episode’s start, follows its optimal stationary policy, and ends episodes using two stopping criteria.One criterion controls episode-length growth; the other stops when visits to a state-action pair double.Source: §1 · p. 2
  • TSDE’s expected regret is bounded by the best available order for weakly communicating MDPs, and numerical results show it outperforms algorithms with the same order in T.The bound also matches the theoretical lower bound in order of T, up to logarithmic factors.Source: §1 · p. 2

2 Problem Formulation

The problem formulation treats the transition model as unknown while assuming known costs, finite state and action spaces, and a Bayesian prior supported on weakly communicating MDPs with bounded span.

2.1 Preliminaries

  • The MDP has finite state and action spaces, a cost function, and transition probabilities; the initial state is known and fixed.Costs are normalized to [0, 1] without loss of generality because the spaces are finite.Source: §2.1 · p. 2
  • A weakly communicating MDP has transient states under every stationary policy and a remaining set whose states can reach one another under some stationary policy.The paper restricts attention to this subclass for meaningful finite-time regret bounds.Source: §2.1 · p. 2
  • For weakly communicating MDPs, the optimal average cost per stage satisfies a Bellman equation, and its minimizing policy is stationary.The value function’s span is defined after normalizing its minimum to zero; the span is its maximum value.Source: §2.1 · p. 3
  • The analyzed model class consists of weakly communicating transition models whose span is bounded by H.The paper denotes this set of transition models by Ω*.Source: §2.1 · p. 3

2.2 Reinforcement Learning for Weakly Communicating MDPs

  • The agent knows the finite spaces and cost function, while the true transition probabilities are drawn randomly before interaction and then remain fixed but unknown.The paper notes that extending algorithms to unknown costs or rewards generally costs a constant factor in the regret bound.Source: §2.2 · p. 3
  • A learning algorithm selects actions from the observed state-and-action history and may randomize over actions.The action at time t is specified by a history-dependent function φ_t.Source: §2.2 · p. 3
  • The Bayesian prior’s support is restricted to transition models that are weakly communicating and have span at most H.The prior is the distribution for the unknown transition parameter θ*.Source: §2.2 · p. 3
  • Bayesian expected regret through time T compares accumulated costs with the optimal per-stage cost, averaging over the prior, transitions, and algorithm randomness.The optimal per-stage cost is J(θ*).Source: §2.2 · p. 3

3 Thompson Sampling with Dynamic Episodes

TSDE samples a model from the current posterior at each episode’s start and follows its optimal stationary policy until either of two dynamic stopping criteria is met. The paper establishes regret guarantees for TSDE, including when the sampled policy is approximate.

3 Thompson Sampling with Dynamic Episodes

  • At each episode’s start, TSDE samples a parameter from the posterior and follows the sampled model’s optimal stationary policy until the linear-growth or state-action visit-doubling criterion triggers.The doubling criterion fires when visits to a state-action pair exceed twice its count at the episode’s start; TSDE needs neither the horizon T nor the span bound H.Source: §3 · pp. 3–4

3.1 Main Result

  • TSDE’s regret bound matches the best available order for weakly communicating MDPs and does not depend on the prior or the optimal policy’s recurrent time.The bound has the same order in H, S, A, and T as the optimistic algorithm cited by the paper.Source: §3.1 · p. 4

3.2 Approximation Error

  • For TSDE, computation error for the optimal stationary policy is only additive to regret; the regret bound would remain of its stated order if each episode’s approximation error satisfies ǫk ≤ 1.Source: §3.2 · p. 5

4 Analysis

The analysis bounds the number of TSDE episodes and adapts posterior-sampling arguments to random episode start times. It decomposes expected regret into three terms and uses the stopping-time property and episode-length rule in bounding them.

4.1 Number of Episodes

  • The analysis bounds the number of macro episodes by SA log(T), which is used to obtain an upper bound on TSDE’s episode count.Macro episodes begin when the state-action visit-doubling criterion triggers.Source: §4.1 · p. 5

4.2 Regret Bound

  • Because episode start times are stopping times, posterior sampling retains its expectation identity for functions of the sampled parameter and episode-start history.This property supports the bound on the first regret term, R0.Source: §4.2 · p. 6
  • The first stopping criterion is essential to bounding episode length by the previous episode’s length, which is known at the start of the current episode.The proof writes regret as R0 + R1 + R2 and bounds these terms separately.Source: §4.2 · p. 7

5 Simulations

Simulations compare TSDE with UCRL2, TSMDP, and Lazy PSRL on randomly generated MDPs and RiverSwim. TSDE leads in the random-MDP experiment and outperforms most comparators in RiverSwim, with TSMDP at one resampling state the exception.

5 Simulations

  • The simulations use randomly generated MDPs and the RiverSwim example to compare TSDE against three algorithms with the same regret order.The comparisons include UCRL2, TSMDP, and Lazy PSRL.Source: §5 · pp. 7–8
  • In randomly generated MDPs, TSDE outperforms UCRL2, TSMDP, and Lazy PSRL.The paper reports a significant regret gap between TSDE and UCRL2 and TSMDP.Source: §5 · p. 8, Figure 1 · p. 8
  • In RiverSwim, TSDE significantly outperforms UCRL2, Lazy PSRL, and TSMDP with s0 = 3, while TSMDP with s0 = 1 performs slightly better.The paper notes that choosing s0 = 1 is not possible when the MDP is unknown in practice.Source: §5 · p. 8, Figure 1 · p. 8

6 Conclusion

TSDE combines dynamic episode stopping with Thompson Sampling and achieves a stated expected-regret bound for weakly communicating MDPs. The conclusion also reports that its linear episode-growth criterion helps balance exploration and exploitation.

6 Conclusion

  • TSDE establishes ˜O(HS√(AT)) expected-regret bounds for the general subclass of weakly communicating MDPs.The conclusion says numerical results validate that TSDE outperforms other learning algorithms for infinite horizon MDPs.Source: §6 · p. 8
  • The conclusion reports that numerical results validate TSDE's advantage over other learning algorithms for infinite horizon MDPs.Source: §6 · p. 8
  • The first stopping criterion limits episode-length growth and is described as a new idea for episodic learning algorithms.The criterion is crucial in the regret-bound proof, and simulations versus Lazy PSRL indicate that it helps balance exploitation and exploration.Source: §6 · p. 8

A Bound on the number of macro episodes

The proof bounds the number of macro episodes by counting how often each state-action pair can trigger one. The doubling stopping rule makes those per-pair counts logarithmic in visits.

A Bound on the number of macro episodes

B Proof of Lemma 4

The proof invokes Assumption 1 to bound the value function and its span by H.

B Proof of Lemma 4

C Proof of Lemma 5

The proof of Lemma 5 uses empirical transition estimates and confidence sets, together with the visit-count doubling rule, to bound terms in its regret expression.

C Proof of Lemma 5

  • The proof bounds each inner-summation term using 0 ≤ v(s′, θt) ≤ H from Assumption 1.Source: C Proof of Lemma 5 · p. 11
  • At the start of episode k, Ntk(z) is the empirical mean for the transition probability, with transition counts defined from observations before tk.Source: C Proof of Lemma 5 · p. 11
  • The proof uses βk(z) as the confidence set used in with δ = 1/T.Source: C Proof of Lemma 5 · p. 11
  • Within an episode, the second stopping criterion ensures Nt(zt) ≤ 2Ntk(zt), which the proof uses to bound the first term in (14).Source: C Proof of Lemma 5 · p. 11

D Proof of Theorem 2

The proof of Theorem 2 derives the first part of the result from the proof of Theorem 1 and uses Lemma 1 to justify its last inequality.

Loading 1709.04570v1…