Reinforcement learning solves average reward tasks in complex state networks
Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
Machine Learning
Summary
Figuring out the best way to act on average over time in certain complex systems can be tricky because some parts of the system behave very differently depending on where you start. The authors looked at systems where these differences create difficulties for learning methods. They broke down the system into smaller parts organized in a hierarchy, making it easier for algorithms to find the best long-term average actions. Their algorithm reliably learns the best strategies and improves over time, even without knowing all the system details. They also made versions that find nearly best strategies faster or with better short-term results.
What this means in practice
- •For autonomous system engineers: Create control policies for robots or vehicles in environments where state dynamics vary across modes, ensuring optimal long-term average performance without full model knowledge.
- •For operations management teams: Develop scheduling and resource allocation strategies in complex systems with multiple operational modes to optimize average cost or throughput over time.
Authors
Huizhen Yu, Isaiah Heidt
Abstract
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 an asynchronous value-iteration-based RL algorithm that requires no model knowledge beyond the MDP's transition graph and 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. Building on this base algorithm, we develop two further algorithms: 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 base algorithm. We provide almost-sure convergence guarantees for all three algorithms and empirically compare their tradeoffs, showing that the latter two also consistently improve transient performance relative to the base algorithm. To our knowledge, these are the first essentially model-free average-reward RL algorithms for general multichain MDPs without reductions to discounted problems.