Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL

Abstract

Reinforcement learning (RL) in episodic, factored Markov decision processes (FMDPs) is studied. We propose an algorithm called FMDP-BF, which leverages the factorization structure of FMDP. The regret of FMDP-BF is shown to be exponentially smaller than that of optimal algorithms designed for non-factored MDPs, and improves on the best previous result for FMDPs~\citep{osband2014near} by a factored of $\sqrt{H|{\mathcal{S}}_i|}$, where $|{\mathcal{S}}_i|$ is the cardinality of the factored state subspace and $H$ is the planning horizon. To show the optimality of our bounds, we also provide a lower bound for FMDP, which indicates that our algorithm is near-optimal w.r.t. timestep $T$, horizon $H$ and factored state-action subspace cardinality. Finally, as an application, we study a new formulation of constrained RL, known as RL with knapsack constraints (RLwK), and provides the first sample-efficient algorithm based on FMDP-BF.

References in corpus (19)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Bandits with Knapsacks
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Learning Near Optimal Policies with Low Inherent Bellman Error
• An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
• Near-optimal Reinforcement Learning in Factored MDPs
• Model-based Reinforcement Learning and the Eluder Dimension
• Minimax Regret Bounds for Reinforcement Learning
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Exploration-Exploitation in Constrained MDPs
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Constrained Upper Confidence Reinforcement Learning
• Constrained episodic reinforcement learning in concave-convex and knapsack settings
• Information-Theoretic Confidence Bounds for Reinforcement Learning
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes

Cited by in corpus (1)

• Provably Efficient Algorithms for Multi-Objective Competitive RL