PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping

Dongruo Zhou, Jiafan He, Quanquan Gu

arXiv:2006.13165v4cs.LGcs.AImath.OCstat.ML

TL;DR

Large state and action spaces motivate feature-based reinforcement learning, but prior guarantees for discounted MDPs required a generative model or strong assumptions. The paper studies linear kernel MDPs and proposes UCLK, which achieves a regret bound and is near-optimal up to a factor depending on the discount rate.

  • Problem

    For discounted MDPs with feature mappings, existing guarantees relied on a generative model or strong assumptions such as ergodicity.

    Source: §1 · p. 2

  • Method

    The paper studies discounted linear kernel MDPs, whose transition kernels are linear in a predefined feature map, and proposes the UCLK algorithm.

    Source: §1 · p. 2

  • Results

    UCLK achieves eO(d√T/(1−γ)^2) regret, and the paper’s lower bound implies near-optimality up to a (1−γ)^−0.5 factor.

    Source: §1 · p. 2

  • Takeaways & Limitations

    UCLK provides the first polynomial regret bound for discounted MDPs without a generative model or strong assumptions such as ergodicity.

    Source: §1 · p. 2

    Without a generative model or further MDP assumptions, some states may never be visited from certain initial states, making sample complexity for finding a near-optimal policy meaningless.

    Source: §1 · p. 2

Abstract

from arXiv · show

Modern tasks in reinforcement learning have large state and action spaces. To deal with them efficiently, one often uses predefined feature mapping to represent states and actions in a low-dimensional space. In this paper, we study reinforcement learning for discounted Markov Decision Processes (MDPs), where the transition kernel can be parameterized as a linear function of certain feature mapping. We propose a novel algorithm that makes use of the feature mapping and obtains a $\tilde O(d\sqrt{T}/(1-\gamma)^2)$ regret, where $d$ is the dimension of the feature space, $T$ is the time horizon and $\gamma$ is the discount factor of the MDP. To the best of our knowledge, this is the first polynomial regret bound without accessing the generative model or making strong assumptions such as ergodicity of the MDP. By constructing a special class of MDPs, we also show that for any algorithms, the regret is lower bounded by $\Omega(d\sqrt{T}/(1-\gamma)^{1.5})$. Our upper and lower bound results together suggest that the proposed reinforcement learning algorithm is near-optimal up to a $(1-\gamma)^{-0.5}$ factor.

1 Introduction

Feature mappings offer a way to handle large state and action spaces, but provable guarantees for discounted MDPs have relied on a generative model or strong assumptions. The paper studies linear kernel MDPs and proposes UCLK, with upper and lower regret bounds.

1 Introduction

  • Feature mappings address large state and action spaces, where traditional tabular methods are computationally intractable.Despite empirical success, the theoretical understanding and fundamental limits of feature-based methods remain understudied.Source: §1 · p. 1
  • Prior guarantees for discounted MDPs with feature mappings relied either on a generative model or on strong assumptions such as uniform ergodicity.The paper frames whether efficient guarantees are possible without either requirement as its motivating question.Source: §1 · p. 2
  • The paper studies discounted linear kernel MDPs, where the transition kernel is a linear function of a predefined d-dimensional feature mapping, and introduces the UCLK algorithm.The model includes MDP classes studied in earlier work as special cases.Source: §1 · p. 2
  • UCLK achieves eO(d√T/(1−γ)^2) regret, the first polynomial regret bound for discounted MDPs without a generative model or strong assumptions such as ergodicity.Its regret is independent of the cardinalities of the state and action spaces.Source: §1 · p. 2
  • Any algorithm has regret at least Ω(d√T/(1−γ)^1.5), making UCLK near-optimal up to a (1−γ)^−0.5 factor.The lower bound uses a specially constructed linear kernel MDP.Source: §1 · p. 2
  • The linear kernel MDP setting is the same as the parameterized transition model or linear mixture model studied in earlier work.The paper notes this connection to Jia et al. (2020) and Ayoub et al. (2020).Source: §1 · p. 2

2 Related Work

Prior work on feature-based reinforcement learning studied both finite-horizon and discounted MDPs, under different model assumptions and learning settings. This paper places its contribution among work on discounted MDPs without a generative model.

Finite-horizon MDPs with feature mappings

  • Finite-horizon feature-based methods studied linear transition and reward models, bilinear transition models, linear Bellman backups, combinations of base models, and low inherent Bellman error.The cited work reports regret, PAC, or other provable guarantees under these different assumptions.Source: §2 · p. 3
  • Jia et al. (2020) and Ayoub et al. (2020) studied linear mixture models in finite-horizon MDPs and established regret lower bounds using a hard tabular MDP.The related-work discussion also notes a negative result where moderate value-function approximation error can yield exponential sample complexity for learning an optimal policy.Source: §2 · p. 3

Discounted MDPs with a generative model

  • For discounted MDPs with a generative model, prior work studied sample complexity for both tabular settings and function approximation.Yang and Wang (2019a) used a d-dimensional transition feature map and gave an optimal eO(d/((1−γ)^3ϵ^2)) sample-complexity guarantee for learning an ϵ-suboptimal policy.Source: §2 · p. 3

Discounted MDPs without a generative model

  • Earlier discounted-MDP work without a generative model focused on sample complexity or regret, including bounds that depend on state and action space sizes.The paper places its own regret-based analysis in this line of work.Source: §2 · p. 4

3 Preliminaires

The paper formulates discounted MDP learning as minimizing cumulative suboptimality and studies a transition model that is linear in a known feature mapping. Its preliminaries define the model class and relate it to earlier MDP formulations.

Preliminaries

  • The MDP formulation allows a countable state space and assumes a deterministic, known reward function, with transition probabilities governing next states.The discount factor satisfies 0≤γ<1.Source: §3 · p. 4

Linear kernel MDPs

  • A linear kernel MDP has a transition probability represented as a linear function of a known feature mapping and an unknown parameter vector.The paper identifies this class with the linear mixture model studied in earlier work.Source: §3 · p. 4

Examples

  • Tabular MDPs are a special case of linear kernel MDPs, with dimension d=|S|^2|A| and features given by natural basis vectors.The paper also gives special-case constructions for MDPs represented by combinations of base transition models.Source: §3 · p. 5

Comparison with linear MDPs

  • Linear kernel MDPs and linear MDPs use different feature mappings, and neither model class contains the other.The former maps state, action, and next state; the latter maps state and action.Source: §3 · p. 5

Regret

  • The online objective is to choose a policy whose expected discounted return approaches the optimal return, measured by cumulative regret over the first T rounds.Regret sums the per-round suboptimality, which is nonnegative; smaller regret means fewer total mistakes, though not necessarily fewer severe mistakes.Source: §3 · pp. 5–6

4 The Proposed Algorithm

UCLK is a multi-epoch algorithm for linear kernel MDPs that alternates planning with policy execution and data collection. Adaptive epoch lengths control policy-switching error, while extended value iteration selects actions using plausible MDPs.

4 The Proposed Algorithm

  • Adaptive epoch lengths control the switching error that arises when UCLK updates its policy.Each epoch's length depends on previous observations rather than being fixed in advance.Source: §4 · p. 6
  • At each epoch's planning phase, UCLK estimates the transition parameter, forms a confidence set, and uses extended value iteration to compute action values.EVI chooses the near-optimal MDP among those induced by the confidence set.Source: §4 · pp. 6–7
  • During execution, UCLK follows the greedy policy, observes the next state, and updates its parameter vector and matrix until a determinant-based stopping rule is met.The epoch ends when det(Σ_t) exceeds twice det(Σ_tk).Source: §4 · p. 7
  • UCLK is online and stores only a vector and matrix, requiring O(d^2) space; Monte Carlo integration can handle its two stated implementation computations in special cases.Those computations are evaluating φV(s, a) and obtaining Q from EVI.Source: §4 · p. 8

5 Main Theory

The paper analyzes UCLK's regret on linear kernel MDPs and compares its upper bound with a lower bound for any algorithm. The bounds match in their dependence on feature dimension and time horizon, while their discount-factor dependence differs.

5 Main Theory

  • UCLK's regret bound is independent of the state- and action-space cardinalities, making the bound applicable to large spaces.The regret bound depends on the feature mapping rather than polynomially on |S| and |A|.Source: §5 · pp. 8–9
  • For tabular MDPs, UCLK's generic bound is worse than Liu and Su (2020) in its dependence on |S| and |A|.The authors note that a tabular-specific confidence set could improve the bound, leaving this for future work.Source: §5 · p. 9
  • Theorem 5.4 gives a regret lower bound for any algorithm on a constructed linear kernel MDP.The stated theorem applies when γ ≥ 2/3, d ≥ 2, and T ≥ max{d^2/225, 5γ}/(1 − γ).Source: §5 · p. 9
  • The upper and lower bounds have matching dependence on d and T, while UCLK's discount-factor dependence is worse by a factor of (1 − γ)^-0.5.The paper describes UCLK as near-optimal with respect to the discount factor up to this factor.Source: §5 · p. 9

6 Proof Sketch of the Main Theory

The proof sketches establish the upper bound through confidence-set coverage, optimistic action values, and control of epoch updates. The lower-bound sketch constructs a two-state linear kernel MDP and uses divergence bounds to analyze learning difficulty.

6.1 Proof Sketch of Theorem 5.1

  • With high probability, the true parameter remains in each epoch's confidence set, and extended value iteration produces action values that upper-bound the optimal action values.The EVI approximation is characterized after a finite number of iterations.Source: §6.1 · pp. 9–10
  • UCLK updates its policy at most 2d log[(λ + dT)/(λ(1 − γ)^2)] times, so the update count is nearly independent of T.The paper contrasts this with finite-horizon feature-mapping algorithms that update every H steps.Source: §6.1 · p. 10
  • The upper-bound proof decomposes regret across epochs and bounds its terms using the confidence and iteration lemmas and an Azuma-Hoeffding inequality.The proof sketch says the complete proofs are deferred to the appendix.Source: §6 · p. 9, §6.1 · p. 10

6.2 Proof Sketch of Theorem 5.4

  • The lower-bound construction uses two states, binary rewards, and action-dependent transitions from x0 parameterized by a vector in Θ.From x1, the transition probabilities are δ to x0 and 1 − δ to x1 for every action.Source: §6.2 · p. 11, Figure 1 · p. 11
  • The proof relates regret to visits to x1 and bounds the divergence between instances whose parameters differ in one coordinate.Lemma 6.8 assumes 2Δ < δ ≤ 1/3.Source: §6.2 · p. 12
  • The proof sketch selects δ = 1 − γ and a Δ depending on d, T, and γ to obtain the final lower-bound result.It computes optimal values at x0 and x1 for the constructed MDP before making this parameter choice.Source: §6.2 · p. 12

7 Conclusion

The paper presents UCLK for linear kernel MDPs and gives upper and lower regret bounds. The bounds leave a factor of (1−γ)^−0.5 gap in their dependence on the discount factor.

7 Conclusion

  • UCLK is proposed as an algorithm for solving linear kernel MDPs.Source: §7 · p. 12
  • The lower bound is Ω(d√T/(1−γ)^1.5) for any algorithm, leaving a (1−γ)^−0.5 gap between the bounds.The gap is identified as an open problem for future work.Source: §7 · p. 12
  • UCLK has regret eO(d√T/(1−γ)^2), the first such polynomial bound for discounted MDPs without a generative model or strong assumptions such as uniform ergodicity.The bound is independent of state- and action-space cardinalities.Source: §7 · p. 12

A Conversion from Sample Complexity to Regret

This section converts an exploration sample-complexity guarantee into a regret bound. It separates rounds with value gap at least ε from the remaining rounds, then optimizes the resulting bound.

A Conversion from Sample Complexity to Regret

B Details of Implementation

The implementation discussion uses Monte Carlo integration to approximate feature-value integrals and reduce storage and computation. Theorem 5.1’s proof bounds regret by analyzing contributions across epochs and controlling the resulting terms.

B Details of Implementation

  • Monte Carlo integration estimates feature-value integrals to ε accuracy using eO(1/ε^2) samples, exploiting the decomposition of the feature mapping into ψ(s) and μ(s,a).Source: B Details of Implementation · pp. 13–14
  • The implementation stores dR function values and has stated time complexity UdRB|A| to obtain them, followed by dB|A| to calculate Q values.Source: B Details of Implementation · p. 14

C.1 Proof of Theorem 5.1

  • Theorem 5.1’s proof divides regret into epoch-based terms and bounds these using confidence-set and martingale arguments.The proof invokes determinant bounds and Azuma–Hoeffding to control terms in the decomposition.Source: §C.1 · pp. 15–18

C.2 Proof of Theorem 5.4

The proof of Theorem 5.4 constructs a two-state MDP family and compares policies across parameter choices. It uses a Pinsker-based argument to bound the differences in observed behavior.

C.2 Proof of Theorem 5.4

  • The construction uses states x0 and x1 with rewards 0 and 1, and derives their optimal values from the Bellman equations.Source: §C.2 · p. 19
  • The argument sums over parameter choices and selects δ and Δ subject to constraints before completing the lower-bound construction.Source: §C.2 · pp. 19, 21, 22
  • The proof compares parameter vectors differing in one coordinate and uses Pinsker’s inequality to control the resulting distributional differences.Source: §C.2 · pp. 19–20

D.1 Proof of Lemma 6.1

The proof chain establishes confidence-set inclusion, bounds on value iterates and update differences, and a determinant-based bound on the number of episodes. Later estimates invoke bounded rewards and parameter constraints.

D.1 Proof of Lemma 6.1

  • The true parameter θ∗ belongs to B ∩ C_k for every 1 ≤ k ≤ K.The proof uses a martingale-difference sequence and a self-normalized concentration bound.Source: §D.1 · p. 22

D.2 Proof of Lemma 6.2

  • The proof uses induction to establish its stated conclusion, while the update obeys Q(u+1)(s,a) = r(s,a) + γePV(u)(s,a) ≤ 1 + γ/(1 − γ) = 1/(1 − γ).Source: §D.2 · p. 23

D.3 Proof of Lemma 6.3

  • Contraction of the maximum operator bounds successive value updates and supports selecting θ_t as a maximizing parameter.The proof concludes by taking θ_t to be the parameter attaining the maximum in (D.8).Source: §D.3 · pp. 23–24

D.4 Proof of Lemma 6.4

  • The determinant-growth argument bounds the episode count by K ≤ 2d log(λ + Td/(λ(1 − γ)^2)).The proof uses a determinant doubling property at episode updates.Source: §D.4 · p. 25

E.1 Proof of Lemma 6.6

  • The expectation-bound proof substitutes inequalities using r(s_t, a_t) ≤ 1 and t − 1 ≤ ∞.The supplied proof passage does not state the resulting bound.Source: §E.1 · p. 25

E.2 Proof of Lemma 6.7

  • The hard-MDP estimate uses the constraints ⟨a, θ⟩ ≥ −Δ ≥ −δ and 2Δ ≤ δ in bounding its terms.The proof also invokes (1 − δ)/δ < T/5.Source: §E.2 · pp. 26–27

E.3 Proof of Lemma 6.8

The proof uses the Markov property to decompose trajectory KL divergence into one-step terms. It treats transitions from x1 as parameter-independent and bounds the x0 transition contribution using a Bernoulli model.

Proof of Lemma 6.8

  • The trajectory KL divergence is decomposed using the Markov property and then bounded through its one-step terms.The proof defines the KL divergence between next-state distributions before bounding the terms.Source: §E.3 · p. 27
  • When the current state is x1, the transition probabilities are identical across θ and θ′, so the corresponding KL term is zero.The construction makes the transition probability at x1 irrelevant to θ.Source: §E.3 · p. 27
  • From x0, the next state follows a Bernoulli distribution with probabilities δ + ⟨a, θ′⟩ and 1 − δ − ⟨a, θ′⟩.The proof bounds the resulting log-ratio expression using Lemma E.1.Source: §E.3 · pp. 27–28
Loading 2006.13165v4…