Finite-Time Bounds for Average-Reward Fitted Q-Iteration
This addresses a gap in offline RL theory for practitioners needing efficient algorithms in non-discounted settings, though it is incremental as it builds on existing Fitted Q-Iteration.
The paper tackles the problem of sample complexity in average-reward offline reinforcement learning with function approximation, establishing the first finite-time bounds for weakly communicating MDPs, a milder assumption than prior work, and shows that an anchor mechanism enables this analysis.
Although there is an extensive body of work characterizing the sample complexity of discounted-return offline RL with function approximations, prior work on the average-reward setting has received significantly less attention, and existing approaches rely on restrictive assumptions, such as ergodicity or linearity of the MDP. In this work, we establish the first sample complexity results for average-reward offline RL with function approximation for weakly communicating MDPs, a much milder assumption. To this end, we introduce Anchored Fitted Q-Iteration, which combines the standard Fitted Q-Iteration with an anchor mechanism. We show that the anchor, which can be interpreted as a form of weight decay, is crucial for enabling finite-time analysis in the average-reward setting. We also extend our finite-time analysis to the setup where the dataset is generated from a single-trajectory rather than IID transitions, again leveraging the anchor mechanism.