PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound

Lin F. Yang, Mengdi Wang

arXiv:1905.10389v2cs.LGstat.ML

TL;DR

Large state-action spaces make RL exploration difficult, while feature-based methods lack sufficient guarantees and some existing bounds depend exponentially on H. The paper proposes MatrixRL, which estimates a low-dimensional transition core using matrix-bandit ideas and extends it to kernel spaces. It reports regret bounds that are near-optimal in time and dimension and polynomial in H, with an open regularity-condition question.

  • Problem

    RL exploration suffers from state-action dimensionality, and existing feature-based methods either lack theoretical guarantees or can have regret exponential in the planning horizon H.

  • Method

    MatrixRL estimates a feature-space transition core by ridge regression and uses confidence-ball optimism for dynamic programming, with a kernelized version based on Gram matrices.

  • Results

    The bounds are near-optimal in T and feature dimension, polynomial in H, and the kernelized method replaces feature dimension with effective kernel dimension.

  • Takeaways & Limitations

    Feature- and kernel-based regret bounds do not depend on state- and action-space sizes, supporting efficient exploration in high-dimensional settings.

  • Takeaways & Limitations

    The paper leaves open whether its regularity condition can be relaxed and whether more efficient confidence-ball construction can further reduce regret.

Abstract

from arXiv · show

Exploration in reinforcement learning (RL) suffers from the curse of dimensionality when the state-action space is large. A common practice is to parameterize the high-dimensional value and policy functions using given features. However existing methods either have no theoretical guarantee or suffer a regret that is exponential in the planning horizon $H$. In this paper, we propose an online RL algorithm, namely the MatrixRL, that leverages ideas from linear bandit to learn a low-dimensional representation of the probability transition model while carefully balancing the exploitation-exploration tradeoff. We show that MatrixRL achieves a regret bound ${O}\big(H^2d\log T\sqrt{T}\big)$ where $d$ is the number of features. MatrixRL has an equivalent kernelized version, which is able to work with an arbitrary kernel Hilbert space without using explicit features. In this case, the kernelized MatrixRL satisfies a regret bound ${O}\big(H^2\widetilde{d}\log T\sqrt{T}\big)$, where $\widetilde{d}$ is the effective dimension of the kernel space. To our best knowledge, for RL using features or kernels, our results are the first regret bounds that are near-optimal in time $T$ and dimension $d$ (or $\widetilde{d}$) and polynomial in the planning horizon $H$.

1 Introduction

The paper studies provably efficient exploration in RL when large state-action spaces motivate feature or kernel representations. It introduces MatrixRL, which learns a low-dimensional transition representation while balancing exploration and exploitation.

  • Motivation: Large or infinite state-action spaces make tabular regret bounds impractical and create the curse of dimensionality.The worst-case tabular dependence on |S||A|T is nonimprovable.
  • Motivation: Features compactly parameterize high-dimensional value and policy functions, but theoretical guarantees for feature-based exploration remain limited.The paper asks how features can enable provably efficient exploration in RL.
  • Motivation: Kernel methods extend the representation to nonlinear dynamics and potentially infinitely many implicit features.The paper asks whether online RL can achieve low regret in an infinite-dimensional kernel space.
  • Our Approach and Main Results: MatrixRL estimates a transition core with ridge regression and constructs a confidence ball for optimistic dynamic programming.The algorithm is framed as a matrix-bandit generalization of linear bandits.
  • Our Approach and Main Results: Kernelized MatrixRL uses Gram-matrix representations and achieves regret depending on the kernel space's effective dimension rather than state- and action-space sizes.This supports efficient exploration in high-dimensional settings, even when the kernel has infinitely many features.
  • Our Approach and Main Results: The feature- and kernel-based bounds are presented as near-optimal in T and dimension, while polynomial in the planning horizon H.The feature result matches the linear-bandit lower bound up to polylogarithmic factors in d and T.

2 Problem Formulation

The paper formulates online episodic RL as learning in a finite-horizon MDP with known rewards and unknown transitions. It assumes the transition model can be embedded in a given feature space through an unknown transition core.

  • MDP Formulation: An episodic MDP contains states, actions, transition distributions, rewards, an initial state, and a planning horizon H.Each episode starts at a prespecified state and lasts H steps before restarting.
  • MDP Formulation: The agent seeks a policy maximizing long-term expected reward from every state-stage pair.The optimal value function and optimal action-value function characterize this objective.
  • Online Learning and Regret: Online learning proceeds episodically, with T = NH total steps across N episodes, and regret compares the algorithm with the optimal policy.The regret definition takes expectation over the random state paths generated under the algorithm.
  • Feature Embedding Assumption: The transition kernel is assumed to be fully embedded in given feature spaces through an unknown matrix M∗ called the transition core.The corresponding kernel condition requires the transition model to belong to a product kernel space.
  • Assumptions: The reward function is assumed known, while unknown linear rewards could be handled with optimistic reward estimation.The resulting extra eO(d√T) regret is described as lower order than the paper's current bounds.

3 RL Exploration in Feature Space

The MatrixRL algorithm uses matrix-bandit ideas to estimate a low-dimensional transition core and balance exploration with exploitation in feature-based RL. Under feature regularity assumptions, it provides regret bounds depending on feature dimension, with a sharper bound under stronger regularity, and extends to kernel spaces.

  • The MatrixRL Algorithm: MatrixRL estimates the unknown transition core by ridge regression and uses a confidence ball for optimistic dynamic programming.The method generalizes linear-bandit exploration to a matrix-valued transition representation.
  • The MatrixRL Algorithm: The algorithm targets regret depending on feature size d rather than the state-action space size.Its episodic implementation maintains a core-matrix estimate and updates it from observed transitions.
  • Regret Bounds for MatrixRL: Under Assumptions 1 and 2, Algorithm 1 achieves the regret bound stated in Theorem 1 after T = NH steps.The supplied theorem passages include the bound’s logarithmic and dimension-dependent terms, while the displayed expression is fragmented across passages.
  • Regret Bounds for MatrixRL: With stronger feature regularity, a Frobenius-norm matrix ball yields a sharper regret bound in Theorem 2.The stronger condition can hold for sparse or highly concentrated feature sets.
  • Scope and Practical Details: The confidence parameter β_n requires knowing the episode count N in advance; a doubling trick adapts to unknown N with only a constant-factor regret increase.The paper identifies prior knowledge of N as a requirement for Theorems 1 and 2.
  • Regret Bounds for MatrixRL: Theorem 2’s regret bound matches the linear-bandit lower bound up to polylogarithmic factors in d and T, making it nearly optimal in d and T.This comparison uses the fact that linear bandits are a special case of RL with planning horizon H = 1.
  • Kernel Extension and Implementation: The method has a kernelized version for reproducing-kernel spaces and can be implemented in space O(d^2) with closed-form computation for each step.Kernelization replaces explicit features with kernel representations, while implementation notes describe sampling-based acceleration for some matrix operations.

4 RL Exploration in Kernel Space

Kernelized MatrixRL replaces explicit features with kernel representations while remaining equivalent to MatrixRL and supports regret analysis through effective kernel dimension.

  • Kernel formulation: Kernelized MatrixRL accesses kernel functions instead of explicit feature maps for state-action and state representations.The method uses reproducing kernel Hilbert spaces with implicit feature maps.
  • Kernel formulation: The algorithm represents MatrixRL features with Gram matrices and uses a dualized Q-function estimator.The kernelized estimator is the dual form of the original estimator.
  • Kernel formulation: Algorithm 2 is equivalent to MatrixRL when kernels are inner products of explicit feature vectors.The kernel version is more general because it can operate without explicit features.
  • Algorithm: Kernelized MatrixRL selects actions by maximizing optimistic Q estimates and records observed transitions for subsequent learning.At each stage, it computes Q estimates, chooses an action, and adds the resulting transition to the reply buffer.
  • Guarantee: The kernel analysis requires regularity assumptions, including an orthonormal-basis condition for the state-feature space.The transition kernel is assumed to belong to the product Hilbert spaces, and the formal guarantee is stated under Assumption 3.
  • Extensions: Kernelized MatrixRL can be extended to unknown rewards using Kernelized Bandit methods.The paper also notes that linear bandits arise as the special case H = 1.

5 Summary

The paper presents MatrixRL and its kernelized counterpart as feature-based approaches to efficient high-dimensional RL exploration with polynomial-horizon regret guarantees.

  • Contributions: MatrixRL estimates a core transition matrix and confidence ball, then computes optimistic Q-functions to balance exploitation and exploration.The method is described as a matrix-bandit approach generalizing linear-bandit ideas.
  • Contributions: The feature-based method achieves regret near-optimal in T and feature dimension d while remaining polynomial in planning horizon H.This guarantee assumes regularity conditions on the feature space.
  • Kernel extension: The kernelized version avoids explicit features and replaces d with the effective dimension e_d of the kernel space.Its regret bounds do not depend on the sizes of the state and action spaces.
  • Open problems: Future work includes relaxing kernel regularity conditions and finding more efficient methods for constructing confidence balls.The paper identifies both issues as open problems for reducing regret or broadening applicability.

A Analysis and Proofs

The analysis proves the main regret theorem by separating performance under a good estimator event from the high-probability proof that the event holds.

  • Proof strategy: The proof first conditions on the true transition core remaining inside the confidence ball throughout learning.Under this event, the desired regret bound is established.
  • Proof strategy: The second proof step shows with high probability that the good estimator event persists throughout online learning.This establishes the confidence required for the regret guarantee.
  • Proof strategy: The Good Estimator Event records whether the true core matrix lies in every confidence ball up to episode n.This event is determined by the game history through episode n.

A.1 Regret Under Good Event

The good-event analysis derives regret from optimism and controls estimation errors through confidence-ball geometry, matrix growth, and martingale concentration.

  • Regret under the good event: The proof rewrites episode regret using the fixed policy selected before that episode and bounds its value difference under the good event.The argument conditions on the history preceding the episode.
  • Regret under the good event: The algorithm plays optimistic actions whenever the good estimator event holds.The optimism lemma is proved by induction over the planning stages.
  • Regret under the good event: The confidence ball bounds estimation error in the direction associated with exploration.A separate lemma controls the additional error introduced by value iteration.
  • Confidence control: Matrix growth is controlled using determinant and trace arguments together with the matrix inversion lemma.The analysis tracks positive-definite matrices and associated quantities across episodes and stages.
  • Confidence control: The high-probability confidence argument constructs martingale differences and applies Freedman’s inequality to control their cumulative deviations.The proof separately bounds step sizes and conditional variances before applying a union bound.

A.3 Proof of Theorem 1

Theorem 1 is proved through a sequence of intermediate lemmas and determinant-based bounds. The proof selects a confidence level and combines these guarantees to establish the theorem.

  • The proof of Theorem 1 is preceded by a proof of Lemma 8.
  • The right-hand side is bounded using an inequality involving ln det(AN+1).
  • The theorem proof sets the confidence level to δ ≤ 1/(NH).
  • The resulting guarantee is obtained by applying Lemmas 13, 15, and 9.

A.4 Proof of Theorem 2

Theorem 2 follows the proof strategy of Theorem 1 while modifying two lemmas to accommodate a different confidence ball. The remaining steps then proceed analogously.

  • Theorem 2 is proved using a strategy nearly identical to the proof of Theorem 1.
  • Lemma 6 is also modified to account for the changed confidence ball.
  • Lemma 5 is modified to establish the required bound for every M ∈ B(2).
  • The rest of the proof follows analogously from Theorem 1.

B Derivation of Kernelization

The kernelization derives value prediction, confidence bounds, and the Q-function estimator using kernel representations rather than explicit features. This yields Kernelized MatrixRL by replacing the feature-based components in Algorithm 1.

  • Kernelized Value Estimation: Kernel matrices represent features of encountered state-action pairs and all states in S.
  • Kernelized Value Estimation: The kernelized construction can represent the required quantities without knowing the explicit features.
  • Kernelized Value Estimation: Kernelized value estimation represents predictions for a vector V ∈ R^S using the kernel.
  • Kernelized Value Estimation: The prediction representation is reduced to kernel matrices through a representation of Θn+1.
  • Kernelized Algorithm: The Q-function estimator is Qn,h(s, a) = r(s, a) + xn(s, a)⊤Vn,h+1 + ηnwn(s, a).The parameter ηn is determined separately.
  • Kernelized Algorithm: Replacing (4) with (9) in Algorithm 1 produces Kernelized MatrixRL, presented as Algorithm 2.

B.1 Proof of Theorem 3

Theorem 3 extends the analysis to kernel spaces by relating the kernel norm to a finite-dimensional matrix norm and preserving the MatrixRL proof structure. Kernel complexity enters through the confidence parameter.

  • The proof allows feature dimensions d and d′ to tend to infinity because the complexity does not depend on them.
  • In the finite-dimensional setting, ∥P∥Hφ×Hψ is equivalent to ∥M∥F.
  • Theorem 3 uses the same algorithm while introducing kernel complexity through the definition of βn.
  • Kernelized MatrixRL and MatrixRL are equivalent when the feature space is finite dimensional.
  • The proof otherwise follows the steps of Theorem 2 and produces a determinant-based bound involving HN · 2H ln det(AN+1).
Loading 1905.10389v2…