Offline Actor-Critic for Average Reward MDPs

William Powell (University of Wisconsin - Madison) · Jeongyeol Kwon (University of Wisconsin - Madison) · Qiaomin Xie (University of Wisconsin - Madison) · Hanbaek Lyu (University of Wisconsin - Madison)

average-rewardcomputationally tractablefixed-point bellman equationinfinite-horizonlinear function classmarkov decision processesmodel misspecification errorsnear-optimal policyoffline policy optimizationpessimistic actor-critic algorithmpolicy gradient sample complexitysecond-order cone programvalue function estimationweak partial data coverage

We study offline policy optimization for infinite-horizon average-reward Markov decision processes (MDPs) with large or infinite state spaces. Specifically, we propose a pessimistic actor-critic algorithm that uses a computationally efficient linear function class for value function estimation. At the core of our method is a critic that computes a pessimistic estimate of the average reward under the current policy, as well as the corresponding policy gradient, by solving a fixed-point Bellman equation, rather than solving a successive sequence of regression problems as in finite horizon settings. This procedure reduces to solving a second-order cone program, which is computationally tractable. Our theoretical analysis is based on a weak partial data coverage assumption, which requires only that the offline data aligns well with the expected feature vector of a comparator policy. Under this condition, we show that our algorithm achieves the optimal sample complexity of O(\varepsilon^{-2}) for learning a near-optimal policy, up to model misspecification errors.