Average-Reward RL for Multichain MDPs: A Hierarchical Decomposition Approach

We study learning optimal policies in average-reward multichain Markov decision processes (MDPs), where the optimal gain may depend on the initial state and recurrence structures vary across policies, creating challenges for reinforcement learning (RL) methods. We propose a largely model-free asynchronous value-iteration-based RL algorithm that leverages Bather's decomposition to hierarchically partition the state space into communicating subsystems and transient states. This decomposition induces a recasting of the global decision problem into structured subproblems, which our algorithm exploits. We show that the algorithm converges to the optimal gain and produces gain-optimal policies after finite time. We further introduce two extensions to improve transient behavior: one approximately solves the multichain average optimality equations to obtain near gain-optimal policies, and another targets near bias-optimality by approximating the optimal bias function and solving an induced average-reward multichain MDP using the proposed base algorithm. We provide almost-sure convergence guarantees for all methods and empirically compare their tradeoffs, demonstrating that both extensions consistently improve transient performance relative to the base algorithm.