We study regret minimization in non-episodic factored Markov decision
processes (FMDPs), where all existing algorithms make the strong assumption
that the factored structure of the FMDP is known to the learner in advance. In
this paper, we provide the first algorithm that learns the structure of the
FMDP while minimizing the regret. Our algorithm is based on the optimism in
face of uncertainty principle, combined with a simple statistical method for
structure learning, and can be implemented efficiently given oracle-access to
an FMDP planner. Moreover, we give a variant of our algorithm that remains
efficient even when the oracle is limited to non-factored actions, which is the
case with almost all existing approximate planners. Finally, we leverage our
techniques to prove a novel lower bound for the known structure case, closing
the gap to the regret bound of Chen et al. [2021].

本研究旨在通过基于乐观面对不确定性原则的算法，结合一种简单的统计方法来实现在学习 FMDP 结构的同时最小化后悔，证明了一个新的已知结构情况下处理的下界，并提出了一种变体算法，即使在现有近似规划器只限于非分解动作的情况下，仍然保持有效。