Bias Span as a Complexity Measure for Average-Reward RL

33 concepts17 papers

In reinforcement learning (RL), we often use a discount factor $\gamma$ to ensure that long-term rewards remain finite and to define a "horizon" of $1/(1-\gamma)$. However, many real-world tasks—like network routing or inventory management—are better modeled as infinite-horizon problems where we seek to maximize the average reward per time step.

Without a discount factor to dampen the future, a new question arises: how do we measure the inherent difficulty of an environment? The answer lies in the bias span, a parameter that captures the maximum possible difference in long-term value between any two starting states.

From Diameter to Span

Early theoretical work often characterized environment complexity using the diameter, which measures the time required to move between any two states. However, the diameter can be excessively large or even infinite in environments with one-way transitions or transient states.

Bartlett et al. proposed a more precise metric: the span of the bias vector. The bias function (or relative value function) represents the total expected reward an agent accumulates starting from a specific state, minus the average reward it would have gained anyway. The span—the difference between the maximum and minimum values of this function—measures how much a starting state actually influences long-term outcomes.

Because the span is always less than or equal to the diameter, using it as a complexity measure results in tighter regret bounds. As Wei et al. and the authors of Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes demonstrate, the span more accurately reflects the actual difficulty of learning an optimal policy, particularly in "weakly communicating" environments where some states are difficult to reach but may not be relevant to the optimal strategy.

The Role of Span in Exploration

In average-reward RL, agents must balance exploration and exploitation without a "stop" time. If an agent is too optimistic, it might spend eternity trying to reach a distant state that promises high rewards but is practically inaccessible.

To prevent this, algorithms like SCAL, introduced by Fruit et al., use the bias span to constrain the agent's optimism. By forcing the value function to stay within a specific span, the agent avoids over-exploring states that offer high optimistic rewards but are "too far" in terms of value difference. This approach allows for sub-linear regret even in environments where the physical diameter is infinite.

Similarly, Bartlett et al. introduced REGAL, which adds a penalty to the reward objective based on the bias span. This regularization prevents the agent from selecting overly complex models that might lead to inefficient exploration.

The Challenge of the Unknown Span

A recurring problem in this field is that the optimal bias span ($H$) is usually unknown. This creates a "chicken-and-egg" dilemma described by Neu and Okolo: to configure a stable optimization algorithm, you need to know the scale of the optimal value function, but that scale is as difficult to estimate as the optimal policy itself.

Many foundational algorithms, such as those discussed by Qian et al. and Hong and Tewari, require a known upper bound on the span to calibrate exploration bonuses or maintain stability. If this bound is too small, the agent may never find the optimal policy; if it is too large, the agent explores too much, leading to suboptimal regret.

Achieving Span-Agnostic Learning

Recent breakthroughs have focused on removing the requirement for a pre-defined span. Boone and Zhang introduced a method for dynamic bias estimation, which tracks "commute times" between states during exploration to calculate the span on the fly. This allows agents to adapt to the environment's complexity without prior knowledge.

Furthermore, Zurek and Chen developed a "horizon calibration" technique and empirical span penalization. Their work achieves minimax optimal sample complexity—the mathematical limit of efficiency—without knowing $H$ in advance. This bridges the gap between theoretical models and practical implementation, where the "intrinsic horizon" of a task is rarely known by the designer.

By shifting the focus from physical connectivity (diameter) to value-based connectivity (span), researchers like Zhang and Ji and Chae et al. have finally matched the mathematical lower bounds for learning in complex, infinite-horizon environments. The span has emerged not just as a technical parameter, but as the fundamental metric governing the complexity of undiscounted reinforcement learning.

Key Foundational Work

REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs (2009) — contributed 3 concept elements to this direction.
Online Regret Bounds for Undiscounted Continuous Reinforcement Learning (2012) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bias_function_span_81f0f813,
  title = {bias function span},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bias-function-span/rdr_81f0f8130517497ab1c4a405fcb96c5e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_bias_function_span_81f0f813_v1,
  title = {bias function span},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bias-function-span/rdr_81f0f8130517497ab1c4a405fcb96c5e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake