Provable Offline Reinforcement Learning for Structured Cyclic MDPs
This work addresses offline RL for complex multi-stage decision problems like healthcare management, though it appears incremental as it builds on existing fitted Q-iteration methods.
The paper tackles the challenge of offline reinforcement learning in cyclic Markov decision processes with heterogeneous stages, where policy optimization at one stage affects others, by proposing a modular framework that decomposes the process into stage-specific sub-problems. It introduces CycleFQI, an extension of fitted Q-iteration, which achieves finite-sample error bounds, mitigates the curse of dimensionality, and shows effectiveness in experiments on simulated and real-world diabetes data.
We introduce a novel cyclic Markov decision process (MDP) framework for multi-step decision problems with heterogeneous stage-specific dynamics, transitions, and discount factors across the cycle. In this setting, offline learning is challenging: optimizing a policy at any stage shifts the state distributions of subsequent stages, propagating mismatch across the cycle. To address this, we propose a modular structural framework that decomposes the cyclic process into stage-wise sub-problems. While generally applicable, we instantiate this principle as CycleFQI, an extension of fitted Q-iteration enabling theoretical analysis and interpretation. It uses a vector of stage-specific Q-functions, tailored to each stage, to capture within-stage sequences and transitions between stages. This modular design enables partial control, allowing some stages to be optimized while others follow predefined policies. We establish finite-sample suboptimality error bounds and derive global convergence rates under Besov regularity, demonstrating that CycleFQI mitigates the curse of dimensionality compared to monolithic baselines. Additionally, we propose a sieve-based method for asymptotic inference of optimal policy values under a margin condition. Experiments on simulated and real-world Type 1 Diabetes data sets demonstrate CycleFQI's effectiveness.