Optimal Approximation of Average Reward Markov Decision Processes

Computational Mathematics and Mathematical Physics. 2025. Vol. 65. No. 3. P. 567–581.

Sapronov Y., Yudin N.

We continue to develop the concept of studying the ε-optimal policy for Average Reward Markov Decision Processes (AMDP) by reducing it to Discounted Markov Decision Processes (DMDP). Existing research often stipulates that the discount factor must not fall below a certain threshold. Typically, this threshold is close to one, and as is well-known, iterative methods used to find the optimal policy for DMDP become less effective as the discount factor approaches this value.

Our work distinguishes itself from existing studies by allowing for inaccuracies in solving the empirical Bellman equation. Despite this, we have managed to maintain the sample complexity that aligns with the latest results. We have succeeded in separating the contributions from the inaccuracy of approximating the transition matrix and the residuals in solving the Bellman equation in the upper estimate so that our findings enable us to determine the total complexity of the epsilon-optimal policy analysis for DMDP across any method with a theoretical foundation in iterative complexity.

Keywords: Markov Decision Processes, вычислительная сложность, обучение с подкреплением, адгритмы и алгоритмическая сложность, размер выборки, sample complexity, reinforcement learning (RL), iteration complexity, марковские процессы принятия решений