Reinforcement Learning of POMDPs using Spectral Methods

By Kamyar Azizzadenesheli, Alessandro Lazaric, Anima Anandkumar. 2016

144 citations recorded by the source corpus.

Author(s): Azizzadenesheli, Kamyar; Lazaric, Alessandro; Anandkumar, Animashree | Abstract: We propose a new reinforcement learning algorithm for partially observable Markov decision processes (POMDP) based on spectral decomposition methods. While spectral methods have been previously employed for consistent learning of (passive) latent variable models such as hidden Markov models, POMDPs are more challenging since the learner interacts with the environment and possibly changes the future observations in the process. We devise a learning algorithm running through episodes, in each episode we employ spectral techniques to learn the POMDP parameters from a trajectory generated by a fixed policy. At the end of the episode, an optimization oracle returns the optimal memoryless planning policy which maximizes the expected reward based on the estimated POMDP model. We prove an order-optimal regret bound with respect to the optimal memoryless policy and efficient scaling with respect to the dimensionality of observation and action spaces.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Mathematical Optimization

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 Management Science and Operations Research

In Reinforcement Learning

In Mathematical Optimization

Citations in the corpus

Surprising Negative Results for Generative Adversarial Tree Search (2018, background): “For Partially Observ-able MDPs, OFU is known to provide a high probability regret upper bound (Azizzadenesheli et al., 2016a).”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, methodology): “[19] deploys OFU in order to propose the high probability regret upper bound for Partially Observable MDPs (POMDPs) using spectral”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “Below we show that CDPs capture classical RL models, including MDPs and POMDPs, and the optimal policies can be expressed as a function of appropriately chosen contexts.”
Deep Variational Reinforcement Learning for POMDPs (2018, methodology): “Instead of optimising an ELBO to learn a maximumlikelihood approximation for the latent representation and corresponding transition and observation model, previous work also tried to learn those dynamics using spectral methods (Azizzadenesheli et al., 2016), a Bayesian approach (Ross et al.”
On Oracle-Efficient PAC RL with Rich Observations (2018, background): “Therefore, this approach, along with related works [27, 28], does not scale to the rich observation settings that we focus on here.”
Near-Optimal Reinforcement Learning in Dynamic Treatment Regimes (2019, background): “Variations of this setting include multi-armed bandits [1], partially-observable MDP [10, 2], and factored MDPs [22].”
Online and Differentially-Private Tensor Decomposition (2016, methodology): “Keywords: Tensor decomposition, tensor power method, online methods, streaming, differential privacy, perturbation analysis.”
Sample-Efficient Deep RL with Generative Adversarial Tree Search (2018, methodology): “Azizzadenesheli et al. (2016a) deploys OFU in order to propose a high probability regret upper bound for Partially Observable MDPs where spectral methods (Anandkumar et al., 2014) is deployed for learning the environment model.”
PAC Reinforcement Learning with Rich Observations (2016, background): “Other theoretical results either make stronger realizability assumptions (c.f., [2]) or scale poorly with problem parameters (e.g., polynomial in the number of functions [22] or the size of the observation space [23]).”
Reinforcement Learning in Rich-Observation MDPs using Spectral Methods (2016, methodology): “Azizzadenesheli et al. [4] recently proposed an algorithm that leverages spectral methods to learn the hidden dynamic of POMDPs and derived a regret scaling as √ Y using fully stochastic policies (which are sub-optimal in ROMDPs).”
Provably efficient RL with Rich Observations via Latent State Decoding (2019, methodology): “Thus we signiﬁcantly generalize beyond the works of Dann et al. (2018) who require deterministic dynamics and Azizzadenesheli et al. (2016a) whose guarantees scale with the observation space size.”
Non-convex Optimization for Machine Learning (2017, background): “…of learning problems including training deep Recurrent Neural Networks [Sedghi and Anandkumar, 2016], Topic Modeling, learning Gaussian Mixture Models and Hidden Markov Models, Independent Component Analysis [Anandkumar et al., 2014], and reinforcement learning [Azizzadenesheli et al., 2016].”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, methodology): “…models used by most of the RL algorithms discussed above assume noise-free state information, whilst many control processes possess output feedback buried in noise and prone to delays (Jaakkola et al., 1995; Bertsekas, 2017; Azizzadenesheli et al., 2016; Toli´c et al., 2012; Bai et al., 2012).”
Sample-Efficient Reinforcement Learning for POMDPs with Linear Function Approximations (2022, background): “However, Azizzadenesheli et al. (2016) and Guo et al. (2016) add extra assumptions such that eﬃcient exploration of the POMDP can always be achieved by running arbitrary policies.”