PaperlayerView exact revision on arXiv

Source-linked AI summary

Modelling transition dynamics in MDPs with RKHS embeddings

Steffen Grunewalder, Guy Lever, Luca Baldassarre, Massi Pontil, Arthur Gretton

arXiv:1206.4655v1cs.LG

TL;DR

MDP dynamic programming requires expectations over transition dynamics, while density estimation and subsequent integration can be costly. This paper estimates those expectation operators with RKHS embeddings and uses them in value iteration, deriving guarantees subject to approximation, embedding, and smoothness conditions.

  • Problem

    Dynamic programming in MDPs requires transition-based expectations, while estimating conditional densities and then computing the integrals can be costly or difficult.

    Source: §1.2 · p. 2

  • Method

    The approach estimates conditional transition expectation operators as RKHS embeddings from samples and applies the estimates in dynamic programming.

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

  • Results

    Value-iteration guarantees bound the gap to the optimal value through RKHS approximation and embedding-estimation errors, with convergence under the stated conditions.

    Source: §3 · p. 5

  • Takeaways & Limitations

    The method avoids density estimates and numerical integration, with expectation computations linear in the points representing an embedding.

    Source: §5 · p. 8

    The guarantees favor smooth value functions, and their stated conditions include smoothness and covariance-operator assumptions.

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

Abstract

from arXiv · show

We propose a new, nonparametric approach to learning and representing transition dynamics in Markov decision processes (MDPs), which can be combined easily with dynamic programming methods for policy optimisation and value estimation. This approach makes use of a recently developed representation of conditional distributions as \emph{embeddings} in a reproducing kernel Hilbert space (RKHS). Such representations bypass the need for estimating transition probabilities or densities, and apply to any domain on which kernels can be defined. This avoids the need to calculate intractable integrals, since expectations are represented as RKHS inner products whose computation has linear complexity in the number of points used to represent the embedding. We provide guarantees for the proposed applications in MDPs: in the context of a value iteration algorithm, we prove convergence to either the optimal policy, or to the closest projection of the optimal policy in our model class (an RKHS), under reasonable assumptions. In experiments, we investigate a learning task in a typical classical control setting (the under-actuated pendulum), and on a navigation problem where only images from a sensor are observed. For policy optimisation we compare with least-squares policy iteration where a Gaussian process is used for value function estimation. For value estimation we also compare to the NPDP method. Our approach achieves better performance in all experiments.

1. Introduction

The paper frames MDP policy optimization as maximizing expected rewards and proposes learning transition expectation operators directly with RKHS embeddings for dynamic programming. This avoids density estimation and numerical integration while offering dimension-independent convergence rates and value-iteration guarantees under stated conditions.

1.1. Preliminaries

  • An MDP policy is chosen to maximize the expected sum of rewards, with value and action-value functions defining optimal and greedy policies.The introduction also states the standard bound relating a greedy policy's value to its action-value approximation error.Source: §1.1 · pp. 1–2

1.2. Overview of the approach

  • The method estimates transition expectation operators with RKHS embeddings, then uses them in dynamic programming for value estimation and policy optimization.This two-stage approach avoids first estimating a conditional density and then numerically integrating it.Source: §1.2 · p. 2

1.3. Advantages of the approach

  • Conditional mean embedding convergence rates are independent of input dimension, unlike kernel density estimation risk, and expectations reduce to RKHS inner products with linear cost in embedding points.Computing embeddings exactly can cost cubic in training-sample size, while approximations can achieve linear cost.Source: §1.3 · p. 2
  • Value-iteration guarantees separate approximation error in the chosen RKHS from embedding-estimation error; the method also applies wherever kernels are defined, including sensor-observation tasks.Related transition-model methods use Gaussian processes or kernel density estimates and typically require numerical integration, whereas this approach learns expectation operators directly.Source: §1.3 · pp. 2–3, §1.4 · p. 3

2. RKHS embeddings of transition probability kernels

The section represents conditional transition expectations as RKHS elements and estimates them from transition samples. It states consistency and value-estimation conditions, then uses the estimates in iterative value updates.

2. RKHS embeddings of transition probability kernels

  • A conditional distribution embedding μ(x,a) represents the next-state expectation operator: its RKHS inner product with f equals the conditional expectation of f(X_t+1).The representation is independent of time by the Markov property.Source: §2 · p. 3
  • Under the conditions of [Thm. 1], the supremum over (x,a) of the RKHS-norm estimation error is O_P(λ^(1/2) + λ^(-3/2)m^(-1/2)); it converges to zero when λ→0 and λ^3m→∞.The accompanying passage describes the first condition as a smoothness assumption on the distribution and refers to a Hilbert-Schmidt condition on covariance operators.Source: §2 · p. 3

Algorithm 1 Estimate Conditional Expectation

  • Algorithm 1 forms a kernel matrix from transition samples and uses a coefficient vector to produce the conditional expectation estimate.The estimate uses a kernel on state-action pairs and a kernel on states.Source: Algorithm 1 Estimate Conditional… · p. 4

Algorithm 2 Estimate Value

  • Algorithm 2 iteratively updates values using rewards and RKHS inner products with conditional embeddings, stopping at the iteration limit or error threshold.It returns a value estimate using the same reward-plus-discounted-inner-product update.Source: Algorithm 2 Estimate Value · p. 4
  • For finite state spaces with a strictly positive definite state kernel, the normalized value-estimation operator is consistent under the stated regularization schedule.The conditions include those of Lemma 2.1 and λ→0 with λ^3m→∞.Source: Algorithm 2 Estimate Value · p. 4

3. Application to MDPs

The section substitutes learned conditional-distribution embeddings for unknown transition expectations in Bellman value iteration. It establishes contraction-based convergence and bounds policy-value error by iteration, RKHS approximation, and embedding-estimation errors.

3. Application to MDPs

  • Learned embedding expectations can replace unknown transition expectations in dynamic programming, including value iteration.For functions in HL, the expectation is approximated by an RKHS inner product; functions outside HL require an additional approximation consideration.Source: §3 · p. 4
  • The approximate Bellman operator is a sup-norm contraction with constant γ, so its iterates converge to a fixed point.The fixed point is unique, and iteration from an arbitrary initial value function converges in sup-norm.Source: §3 · pp. 4–5
  • The policy-value error bound combines finite-iteration error, approximation of V* in HL, and embedding-estimation error.The approximation term favors value functions close to the RKHS model class; the embedding term depends on embedding accuracy and the RKHS norm of the approximant.Source: §3 · p. 5
  • When |X| is finite and L is strictly positive definite, policy-value error converges to zero in estimated-data probability under Lemma 2.2 conditions.In this setting, all real-valued functions lie in the associated RKHS and the embeddings converge under the stated conditions.Source: §3 · pp. 5–6
  • After embeddings are learned, approximate value iteration costs O(m^2|A|κ), and applying the policy costs O(m|A|T).An incomplete-Cholesky sparse embedding reduces embedding-learning cost from cubic to linear in m; subsequent expectations cost O(ℓ), generally ℓ≪m.Source: §3 · p. 6

4. Experiments

Three experiments evaluate embedding-based value estimation and policy optimization, comparing them with LSPI and, for value estimation, NPDP. The approach achieves better performance across the experiments.

4. Experiments

  • Across all three experiments, the approach achieved better performance than the compared methods.Source: §4 · p. 6

4.1. Experiment 1

  • In the 50 × 50 fully observed navigation task, the 5,000-sample policy outperformed the 1,000-sample policy, and estimated values were close to true values.Source: Figure 1 · p. 6, §4.1 · p. 6

4.2. Experiment 2

  • The embedding estimator had significantly lower value-prediction error and ran 50–110 times faster than NPDP; GP-based LSPI improved slowly after 500 samples.Source: Figure 2 · p. 7

4.3. Experiment 3

  • With 4,000 image inputs, the policy was nearly perfect in the goal room but degraded in the ambiguous corridor; GP-based LSPI did not improve as sample counts rose.Source: Figure 3 · p. 7, §4.3 · pp. 7–8

5. Conclusions and Outlook

The paper applies RKHS embeddings to learn expectation operators for MDP transition dynamics, particularly for dynamic programming. It identifies extensions to more complex spaces and non-iid sampling as future work.

  • The proposed RKHS-embedding approach learns expectation operators for MDP transition dynamics, especially for use in dynamic programming.Source: §5 · p. 8
  • Its value-iteration guarantees depend partly on how well the optimal value can be approximated in the chosen RKHS model class.Source: §5 · p. 8
  • Future work includes more complex state and action spaces, convergence results for continuous states, and sampling beyond the assumed iid setting.Source: §5 · p. 8

Related papers

Loading 1206.4655v1…