Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
arXiv:2006.13405
Abstract
We study minimax optimal reinforcement learning in episodic factored Markov decision processes (FMDPs), which are MDPs with conditionally independent transition components. Assuming the factorization is known, we propose two model-based algorithms. The first one achieves minimax optimal regret guarantees for a rich class of factored structures, while the second one enjoys better computational complexity with a slightly worse regret. A key new ingredient of our algorithms is the design of a bonus term to guide exploration. We complement our algorithms by presenting several structure-dependent lower bounds on regret for FMDPs that reveal the difficulty hiding in the intricacy of the structures.
arXiv comment54 pages
References in corpus (9)
- Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
- (More) Efficient Reinforcement Learning via Posterior Sampling
- Empirical Bernstein Bounds and Sample Variance Penalization
- Policy Iteration for Factored MDPs
- Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
- Near-optimal Reinforcement Learning in Factored MDPs
- Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
- Variance Reduction Methods for Sublinear Reinforcement Learning
- Policy Certificates: Towards Accountable Reinforcement Learning