Modelling transition dynamics in MDPs with RKHS embeddings

By Steffen Grünewälder, Guy Lever, Luca Baldassarre, Massimiliano Pontil, Arthur Gretton. 2012

140 citations recorded by the source corpus.

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 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.

Subfields: Artificial Intelligence, Reinforcement Learning, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Reinforcement Learning

In Probabilistic & Bayesian Methods

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “Nevertheless, Grünewälder et al. (2012) gives a more rigorous account of this perspective.”
Doubly Robust Off-policy Value Evaluation for Reinforcement Learning (2015, methodology): “either apply function approximation to fitting M̂ (Jong & Stone, 2007; Grünewälder et al., 2012), or to fitting the value function directly (Bertsekas & Tsitsiklis, 1996; Sutton & Barto, 1998; Dann et al.”
Hilbert Space Embeddings of POMDPs (2012, methodology): “(α ′ a,õi , d−1) end if end for end for Set: Vd(α) = max a∈A Qd(α, a), πd(α) = argmax a∈A Qd(α, a) end if vectors [Grunewalder et al., 2012].”
Conditional mean embeddings as regressors (2012, methodology): “Conditional mean embeddings have been successfully applied to inference in graphical models, reinforcement learning, subspace selection, and conditional independence testing (Fukumizu et al., 2008; 2009; Song et al., 2009; 2010; Grünewälder et al., 2012).”
Iterative Value-Aware Model Learning (2018, result): “6 of Györfi et al. [2002]. For smaller function spaces, such as the p-dimensional linear function approximator mentioned above, the behaviour of the metric entropy is p log( 1ε ), which can be seen as having α → 0 with a certain rate, For many examples of the covering number and metric entropy resul”
Learning from Conditional Distributions via Dual Kernel Embeddings (2016, methodology): “Instead of plugging the embedded MDP into value iteration for policy evaluation in [11], which is not suitable for dynamics random feature embeddings, we propose new algorithms which apply the (functional) stochastic gradient algorithm to regularized Bellman error (16) with respect to V (·) in kerne”
Sparse multi-task reinforcement learning (2014, unknown): “A similar assumption has been previously used in [9] where the transition P is embedded in a RKHS.”
Kernel Embeddings of Conditional Distributions: A Unified Kernel Framework for Nonparametric Inference in Graphical Models (2013, methodology): “In this paper, we will review the recent development of nonparametric inference with kernel embeddings of conditional distributions [4, 5, 6, 7, 8, 9, 10, 11, 12], and provide a novel, unified kernel framework for addressing a broad class of challenging problems in graphical models.”
The Nonparametric Kernel Bayes Smoother (2016, methodology): “Examples include the nonparametric kernel Bayes’ filter (nKB-filter) on discrete-time time-invariant state space models [10] and the Semiparametric kernel Monte-Carlo filter (KMC-filter) [16], as well as methods for dynamical system modeling and reinforcement learning applications [14, 21, 23, 4, 3,”
Non-parametric Policy Search with Limited Information Loss (2017, methodology): “On the one hand, we consider the non-parametric value-function based methods introduced by Grünewälder et al. (2012b) and Pazis and Parr (2011).”
A Survey of Preference-Based Reinforcement Learning Methods (2017, background): “Hence, many model-based approaches try to learn the dynamics based on observed transitions (Grünewälder et al., 2012).”
Abstraction Selection in Model-based Reinforcement Learning (2015, methodology): “…(Sutton & Barto, 1998), policy-gradient methods (Sutton et al., 1999), kernel RL and related non-parametric dynamic programming algorithms (Ormoneit & Sen, 2002; Lever et al., 2012), and pre-processing with state abstraction/aggregation followed by standard RL algorithms (Li et al., 2006).”
Path Integral Control by Reproducing Kernel Hilbert Space Embedding (2012, background): “In related work, [Grünewälder et al., 2012] recently proposed to utilise RKHS embeddings of the transition probability for computation value functions in MDPs.”
Organizing Experience: a Deeper Look at Replay Mechanisms for Sample-Based Planning in Continuous State Domains (2018, background): “, 2016; Pires and Szepesvári, 2016], kernel-based RL (KBRL) [Ormoneit and Sen, 2002], and kernel mean embeddings (KME) for RL [Grunewalder et al., 2012; Van Hoof et al., 2015; Lever et al., 2016].”