Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL

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