Regret Minimization in Factored MDPs with Endogenous and Exogenous Factors

We study regret minimization in non-episodic factored MDPs whose state has an exogenous part, such as the demand arriving at a server, whose transitions do not depend on the action, and an endogenous part whose transitions do. Existing factored-MDP algorithms treat every factor alike and explore the exogenous factors as if actions could inform them, and the literature on MDPs with exogenous inputs exploits the split only under restrictions on the reward or on the endogenous dynamics. We allow the reward to depend jointly on both parts and the action, and the endogenous dynamics to be unknown and stochastic. Our algorithm, Hybrid-DORL, keeps UCRL2 style optimism on every factor but pools the visit counts of each exogenous factor across actions, since no action changes how often such a factor is observed. Its regret is $\tilde{O}(\sqrt{T})$ with a $\sqrt{|\mathcal{A}|}$ factor on the endogenous factors only, and a matching lower bound shows that this dependence on the action count is tight. The algorithm is oracle-efficient: it plans on an augmented factored MDP with a standard planning oracle. Moreover, when the exogenous transitions are i.i.d. a plug-in variant needs neither optimism nor augmentation on the exogenous part: the prefactor falls from the diameter to its endogenous half and the augmented MDP shrinks by a factor exponential in the number of exogenous factors. In experiments Hybrid-DORL has lower regret than every baseline, its advantage over the best baseline grows with the number of actions as the bounds say, and the plug-in variant matches its regret at a fraction of the planning time.