Near-optimal Reinforcement Learning in Factored MDPs

Abstract

Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer $\Omega (\sqrt{SAT})$ regret on some MDP, where $T$ is the elapsed time and $S$ and $A$ are the cardinalities of the state and action spaces. This implies $T=\Omega (SA)$ time to guarantee a near-optimal policy. In many settings of practical interest, due to the curse of dimensionality, $S$ and $A$ can be so enormous that this learning time is unacceptable. We establish that, if the system is known to be a \emph{factored} MDP, it is possible to achieve regret that scales polynomially in the number of \emph{parameters} encoding the factored MDP, which may be exponentially smaller than $S$ or $A$. We provide two algorithms that satisfy near-optimal regret bounds in this context: posterior sampling reinforcement learning (PSRL) and an upper confidence bound algorithm (UCRL-Factored).

References in corpus (2)

• Policy Iteration for Factored MDPs
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

Cited by in corpus (20)

• A Survey of Zero-shot Generalisation in Deep Reinforcement Learning
• Reinforcement Learning in Healthcare: A Survey
• Learning Near Optimal Policies with Low Inherent Bellman Error
• A Tutorial on Thompson Sampling
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Exploratory Grasping: Asymptotically Optimal Algorithms for Grasping Challenging Polyhedral Objects
• Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Approximate Exploration through State Abstraction
• Causal Markov Decision Processes: Learning Good Interventions Efficiently
• Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Thompson Sampling in Non-Episodic Restless Bandits
• Asymptotically Optimal Sequential Experimentation Under Generalized Ranking
• Model-Invariant State Abstractions for Model-Based Reinforcement Learning
• Myopic Bayesian Design of Experiments via Posterior Sampling and Probabilistic Programming
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Improved Exploration in Factored Average-Reward MDPs