Bather-Decomposition-Driven Average-Reward RL for Multichain MDPs: Three Algorithms with Almost-Sure Convergence and Improved Transient Performance
This work proposes three asynchronous value-iteration-based reinforcement learning algorithms for average-reward multichain MDPs: a base algorithm uses Bather's unique hierarchical decomposition to partition the state space into communicating subsystems and transient states, estimates each subsystem's gain via RVI Q-learning, and solves an aggregated optimal stopping problem via Q-learning, converging almost surely to the optimal gain and producing gain-optimal policies after finite time; two further algorithms approximately solve the average optimality equations for near gain-optimal policies and approximate the optimal bias function for near bias-optimal policies, with experiments showing the latter two improve transient performance while remaining near gain-optimal.