Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
This work addresses efficient reinforcement learning in complex structured environments, representing an incremental advance with specific theoretical guarantees.
The authors tackled reinforcement learning in factored Markov decision processes by proposing two model-based algorithms with minimax optimal regret guarantees for known factorizations, achieving optimal regret for rich factored structures and better computational complexity with slightly worse regret.
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.