Reinforcement Learning Algorithms for Average-Payoff Markovian Decision Processes

Satinder P. SinghAAAI 1994

Abstract

This paper introduces a formal framework for reinforcement learning (RL) in average-payoff Markovian Decision Processes (MDPs). By deriving four new algorithms from the Bellman equations using stochastic approximation, we bridge the gap between classical dynamic programming and model-free RL for tasks where the objective is to maximize the average reward per time step. Empirical results on randomly generated MDPs demonstrate that these algorithms—analogous to TD(0) and Q-learning—effectively learn relative value functions and converge reliably to optimal policies.

Introduction

In the early 1990s, reinforcement learning research was predominantly focused on discounted-payoff problems. While discounting is useful in many contexts, it is less suitable for tasks like foraging, queuing, or robotics, where the goal is to optimize long-term steady-state performance and every time step is equally important. In such scenarios, optimal behavior often manifests as a repeating loop or limit cycle.

Prior to this work, average-payoff RL was largely addressed through heuristic methods, most notably Schwartz’s R-learning (1993). This paper provides a rigorous mathematical foundation for average-payoff RL by deriving algorithms directly from the Bellman equations for average-payoff MDPs.

Methods

The core technical contribution of this work is the derivation of four RL algorithms using stochastic approximation. This approach replaces deterministic dynamic programming backup operators with random operators that sample transitions through experience. A key concept introduced is the relative value function, which represents the long-term difference in total payoff gained by starting in one state versus another, rather than an absolute sum. This "grounding" of values (e.g., setting a reference state's value to zero) is essential for numerical stability.

Proposed Algorithms

  • Algorithms 1 & 2 (Policy Evaluation): Designed to estimate the relative values of states for a fixed policy. Algorithm 1 is a direct analog to TD(0), while Algorithm 2 uses a sample average to estimate mean payoff.
  • Algorithms 3 & 4 (Optimal Control): Designed to find the optimal policy. Algorithm 3 improves upon R-learning by updating the estimated average payoff ($\rho$) at every time step. Algorithm 4 estimates $\rho$ specifically as the sample average of payoffs received during greedy (optimal) actions.

Experimental Results

The algorithms were evaluated on randomly constructed MDPs of varying complexity, including small-scale (20 states, 5 actions) and medium-scale (100 states, 10 actions) environments. The transition probabilities and payoff matrices were generated randomly to test the generalizability of the methods.

Convergence of policy evaluation algorithms (1 & 2) on a 20-state MDP.

As shown in Figure 1, the policy evaluation algorithms successfully converge toward the correct relative value functions. The absolute cumulative error drops sharply and stabilizes within the first few hundred thousand state visits.

Convergence of optimal control algorithms (3 & 4) on a 20-state MDP.

Figure 2 illustrates the performance of the optimal control algorithms. Both Algorithm 3 and Algorithm 4 demonstrate robust convergence. Notably, the paper suggests that updating the average payoff estimate on every step (as in Algorithm 3) is more efficient than updating only on greedy steps, as the optimal average payoff is a global property that remains relevant during exploration.

Discussion and Future Work

By moving average-payoff RL from a heuristic "hack" to a mathematically grounded method, this work provides a stable foundation for long-term reward optimization. The empirical results confirm that grounding relative values and utilizing frequent updates for global parameters like $\rho$ are critical for stability and efficiency.

Limitations of this study include the focus on discrete state spaces and the use of simple Boltzmann exploration. Future work should investigate the integration of these algorithms with function approximation (e.g., neural networks) for high-dimensional tasks and explore more sophisticated exploration-exploitation strategies tailored for average-payoff environments.

Summary updated

BibTeX
@inproceedings{singh1994reinforcement,
  author = {Satinder P. Singh},
  title = {{Reinforcement Learning Algorithms for Average-Payoff Markovian Decision Processes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure