An Average-Reward Reinforcement Learning Algorithm for Computing Bias-Optimal Policies

Sridhar MahadevanAAAI 1996 · OpenReview

Abstract

Average-reward reinforcement learning (ARL) is an undiscounted optimality framework that is generally applicable to a broad range of control tasks. ARL computes gain-optimal control policies that maximize the expected payoff per step. However, gain-optimality has some intrinsic limitations as an optimality criterion, since for example, it cannot distinguish between different policies that all reach an absorbing goal state, but incur varying costs. A more selective criterion is bias optimality, which can filter gain-optimal policies to select those that reach absorbing goals with the minimum cost. While several ARL algorithms for computing gain-optimal policies have been proposed, none of these algorithms can guarantee bias optimality, since this requires solving at least two nested optimality equations. In this paper, we describe a novel model-based ARL algorithm for computing bias-optimal policies. We test the proposed algorithm using an admission control queuing system, and show that it is able to utilize the queue much more efficiently than a gain-optimal method by learning bias-optimal policies.

The Challenge of Average-Reward Optimality

In Reinforcement Learning, the "average-reward" framework is popular for cyclical tasks—such as robotics or factory scheduling—because it focuses on the expected payoff per step. However, this criterion is often "unselective."

A standard ARL algorithm is "gain-optimal," meaning it maximizes the long-term average reward. The problem arises when multiple policies achieve the same long-term average but differ in their transient behavior. For instance, if two paths reach a steady-state reward, but one takes 10 steps and the other takes 30, a gain-optimal algorithm sees them as identical. It is "blind" to the initial cost or time taken to reach that steady state.

Relationship between policy sets: Bias-optimal policies are a refined subset of gain-optimal policies.

To address this, the authors target bias optimality. As shown in the figure above, bias-optimal policies are a subset of gain-optimal policies. They act as a tie-breaker, selecting the gain-optimal policy with the best "start-up" performance or minimum transient cost.

A Model-Based Approach to Bias Optimality

The authors propose a novel model-based ARL algorithm specifically for "unichain" Markov Decision Processes (MDPs). The core innovation lies in solving two nested optimality equations simultaneously.

Technical Features

  • Nested Optimality Equations: Unlike standard ARL which solves a single Bellman equation for average reward, this algorithm solves two. The first identifies the set of gain-optimal actions, while the second filters this set to find bias-optimal ones.
  • Simultaneous Solving: To avoid error propagation from sequential solving, the algorithm interleaves the updates for average reward and "bias offset" estimates.
  • Online Model Learning: The algorithm builds an internal model of the environment by tracking transition probabilities ($P_{ij}$) and expected rewards ($r$) from experience.
  • Normalization: Numerical stability is maintained by "grounding" values—setting the reward and bias of a specific reference state to zero.

Experimental Evaluation

The algorithm was evaluated on two synthetic control environments:

  1. A 3-state MDP: A toy problem designed to demonstrate that standard ARL cannot distinguish between specific policies that differ only in transient rewards, whereas the new algorithm identifies the bias-optimal choice.
  2. M/M/1 Admission Control Queuing System: A classic operations research problem where a controller decides whether to admit or reject arriving jobs to maximize profit while minimizing holding costs.

Performance Results

The algorithm was tested against a simplified gain-optimal version across 600 different parameter combinations for the queuing system. The results demonstrate that bias optimality is essential for practical efficiency.

Queue size increase achieved by bias-optimal policies compared to gain-optimal policies across various system parameters.

As seen in the table above, the bias-optimal policy utilizes the queue much more efficiently. In over 100 cases, improvements of 25% or more in queue utilization were observed. In the best-case scenario (top row), the bias-optimal approach increased the average queue size by 96.4% compared to the gain-optimal method, without any decrease in the average reward.

Conclusion and Future Work

This research highlights that bias optimality is crucial for systems like inventory control or queuing, where multiple policies might yield the same long-term average profit but differ significantly in the "debt" or startup costs they incur. The proposed algorithm successfully identifies these superior policies where previous methods like R-learning or H-learning typically fail.

While the algorithm performs well in practice, future work includes developing a formal mathematical proof of convergence and extending the method to model-free architectures to handle larger state spaces and more complex real-world tasks.

Summary updated

Abstract

Average-reward reinforcement learning (ARL) is an undiscounted optimality framework that is generally applicable to a broad range of control tasks. ARL computes gain-optimal control policies that maximize the expected payoff per step. However, gainoptimality has some intrinsic limitations as an optimality criterion, since for example, it cannot distinguish between different policies that all reach an absorbing goal state, but incur varying costs. A more selective criterion is bias optimality, which can filter gain-optimal policies to select those that reach absorbing goals with the minimum cost. While several ARL algorithms for computing gain-optimal policies have been proposed, none of these algorithms can guarantee bias optimality, since this requires solving at least two nested optimality equations. In this paper, we describe a novel model-based ARL algorithm for computing bias-optimal policies. We test the proposed algorithm using an admission control queuing system, and show that it is able to utilize the queue much more efficiently than a gain-optimal method by learning bias-optimal policies.
BibTeX
@inproceedings{mahadevan1996average,
  author = {Sridhar Mahadevan},
  title = {{An Average-Reward Reinforcement Learning Algorithm for Computing Bias-Optimal Policies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
  url = {https://openreview.net/forum?id=ByNoNTe_-H},
}
Figure