Bather-Decomposition-Driven Average-Reward RL for Multichain MDPs: Three Algorithms with Almost-Sure Convergence and Improved Transient Performance

The base algorithm converges almost surely to the optimal gain vector and produces gain-optimal policies after finite time, requiring no model knowledge beyond the MDP's transition graph. Prior work largely reduces the average-reward problem to discounted problems via a vanishing discount factor, or handles only a single communicating class with a model-based approach; this work tackles the multichain problem directly by exploiting Bather's unique hierarchical decomposition, recasting the global problem into average-reward subproblems within each communicating subsystem and an aggregated optimal stopping problem. The authors provide proofs of Theorem 3.1 (convergence of gain estimates) and Theorem 3.2 (finite-time attainment of gain-optimality), relying on RVI Q-learning convergence in communicating MDPs, properness of all stationary policies in the aggregated OSP (Lemma 7.2), and vanishing stopping-reward errors.

The second algorithm approximately solves the full multichain average optimality equations by extending sub-MDP AOE solutions, yielding near gain-optimal policies with gain suboptimality bounded in terms of algorithmic parameters. The base algorithm only obtains partial relative-value solutions from subsystem-level AOEs that do not generally combine into a full AOE solution; this algorithm uses a two-threshold mechanism to stabilize action constraint sets and a three-way partition in finite time, and applies penalties to certain states to ensure stability of undiscounted total-reward Q-learning. Theorem 4.1 establishes almost-sure convergence of the Q-learning iterates to the unique solution of a perturbed AOE, and Theorem 4.2 provides eventual performance bounds on the induced policy's gain suboptimality, showing eventual gain-optimality for sufficiently small parameters.

The third algorithm approximates the optimal bias function via discounted approximations and solves an induced average-reward multichain MDP, yielding near bias-optimal policies that improve transient performance while remaining near gain-optimal. Bias optimality is a stronger criterion than gain optimality, distinguishing among gain-optimal policies by transient reward behavior; this algorithm shifts rewards by the exact optimal gain obtained from the base algorithm, making discounted value functions uniformly bounded and avoiding the divergence typical of direct discounted approximation. Theorem 5.2 provides gain-optimality conditions and bias-optimality error bounds, Proposition 5.1 gives statewise bias bounds for gain-optimal states, and Proposition 5.2 gives necessary and sufficient conditions for bias optimality.

On 100 randomly generated multichain MDPs, the base algorithm achieves the highest fraction of gain-optimal states, Algorithm 2 achieves the best transient performance with slightly reduced gain-optimality, and Algorithm 3 provides a favorable compromise with transient performance close to Algorithm 2 and the bias-optimal benchmark. The experiments directly compare the three algorithms against a discounted Q-learning baseline and use a discount policy iteration algorithm with the true MDP model as an exact bias-optimal benchmark, reporting per-MDP results to validate aggregate trends. The experiments are preliminary, with the authors stating a more extensive empirical evaluation is in progress; round-robin updates are used for reproducibility, while the theoretical results hold under general asynchronous exploration schemes.

The work targets finite-state, finite-action multichain MDPs, and the algorithms assume knowledge of the transition graph (the set of possible successor states for each state-action pair) but not transition probabilities. The authors note this assumption is natural in simulation-based settings where possible successor states can be enumerated from a simulator's code or interface even when transition probabilities are difficult to compute or depend on unobserved factors. Because the decomposition depends only on transition structure, the authors suggest it may suit continual learning settings where preferences evolve or transition probabilities vary over time but the environment's transition structure remains stable. Combined with quantization-based approximation methods, the algorithms can also be applied to infinite-space MDPs obtained as discrete-time approximations of continuous-time stochastic control problems, without requiring strong ergodicity conditions. The authors also note that sub-policies learned within each class are closely analogous to options, suggesting a principled basis for option discovery and reuse.

The performance guarantees are eventual: the algorithms attain the stated optimality properties after finite time almost surely but do not certify when this has occurred, differing from high-probability policy identification results. The experiments are preliminary, with the authors stating a more extensive empirical evaluation is in progress, and they do not directly compare policy bias, instead measuring transient performance by expected cumulative reward before entering a recurrent class. The authors note that per-MDP results show occasional gain suboptimality for Algorithms 2 and 3, which they expect to stem from approximation error, and future work will verify why these large failures occasionally occur and investigate sensitivity to parameter choices. Removing the transition-graph assumption, online discovery and maintenance of Bather's decomposition, and adaptive parameter tuning are all listed as future directions.