Reinforcement Learning in Rich-Observation MDPs using Spectral Methods

By Kamyar Azizzadenesheli, Alessandro Lazaric, Anima Anandkumar. 2016

31 citations recorded by the source corpus.

Reinforcement learning (RL) in Markov decision processes (MDPs) with large state spaces is a challenging problem. The performance of standard RL algorithms degrades drastically with the dimensionality of state space. However, in practice, these large MDPs typically incorporate a latent or hidden low-dimensional structure. In this paper, we study the setting of rich-observation Markov decision processes (ROMDP), where there are a small number of hidden states which possess an injective mapping to the observation states. In other words, every observation state is generated through a single hidden state, and this mapping is unknown a priori. We introduce a spectral decomposition method that consistently learns this mapping, and more importantly, achieves it with low regret. The estimated mapping is integrated into an optimistic RL algorithm (UCRL), which operates on the estimated hidden space. We derive finite-time regret bounds for our algorithm with a weak dependence on the dimensionality of the observed space. In fact, our algorithm asymptotically achieves the same average regret as the oracle UCRL algorithm, which has the knowledge of the mapping from hidden to observed spaces. Thus, we derive an efficient spectral RL algorithm for ROMDPs.

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

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

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, background): “Even though the theoretical RL addresses the exploration and exploitation trade-offs, these problems are still prominent in empirical reinforcement learning research [8], [27], [28].”
On Oracle-Efficient PAC RL with Rich Observations (2018, background): “We construct a family of MDPs as shown in Figure 2 that encodes the 3-SAT problem for this formula as follows: For each variable x i there are two terminal states x 1 i and x 0 i corresponding to the Boolean assignment to the variable.”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, background): “, 2008), Markov process with rich observations (Azizzadenesheli et al., 2016), and so on.”
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.”
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.”