A Harmonic Mean Formulation of Average Reward Reinforcement Learning in SMDPs

Technical Summary: A Harmonic Mean Formulation for Reinforcement Learning with Average Reward in SMDPs

1. Problem Statement

The work addresses the challenge of optimizing the average, undiscounted reward in Semi-Markov Decision Processes (SMDPs) with an infinite horizon. Unlike standard Markov Decision Processes (MDPs), where actions consume a fixed time unit, SMDPs involve actions that stochastically generate both rewards and varying durations (sojourn times). The goal is to maximize the average reward rate (reward per time unit) rather than the cumulative total reward.

Existing model-free algorithms for this setting, particularly SMART and Relaxed-SMART, suffer from critical limitations when rewards and durations are non-stationary or dependent:

• SMART relies on the long-term sample mean (total reward divided by total time). This approach is sensitive to noise; it assumes stationarity, can be dominated by outliers, or fails to adapt to regime shifts in non-stationary environments.
• Relaxed-SMART attempts to handle non-stationarity by using Exponential Moving Averages (EMA) for both rewards and durations and subsequently forming their ratio. However, this method approximates the average rate as the ratio of arithmetic means. The work demonstrates that this approximation is mathematically correct only if rewards and durations are independent. If they are correlated (non-linearly linked), the ratio of means yields an incorrect estimate of the true average rate.

2. Methodology

The authors propose a novel approach based on the Harmonic Mean, the theoretically correct operator for averaging rates (e.g., Speed = Distance/Time).

The Limitation of the Harmonic Mean:
Although the harmonic mean represents the correct aggregation for rates, its standard definition is unsuitable for general Reinforcement Learning (RL) because:

1. It is undefined for zero values (division by zero).
2. It loses the property of "internality" (the mean lies between the minimum and maximum) when values have mixed signs (positive and negative rewards).

The Modified Harmonic Mean Operator ($\mathcal{H}$):
To overcome these limitations, the authors introduce a modified harmonic mean operator ($\mathcal{H}$). This operator:

• Partitions the data into three sets: positive rewards ($X_+$), negative rewards ($X_-$), and zero rewards ($X_0$).
• Calculates the standard harmonic mean separately for the positive and negative subsets.
• Computes a weighted arithmetic mean of these results, treating zero values as a value of 0.
• Theoretical Properties: The authors prove that $\mathcal{H}$ is a general mean (satisfying internality, idempotency, symmetry, and monotonicity) and generalizes the standard harmonic mean where the latter is defined. However, they prove that it is not a quasi-arithmetic mean, distinguishing it from the class encompassing standard arithmetic, geometric, and harmonic means.

Harmonic R-Learning Algorithm:
The authors integrate $\mathcal{H}$ into a model-free RL algorithm named Harmonic R-Learning.

• It follows the structural update rules of R-Learning and SMART (updating Q-values based on marginal reward relative to the average rate).
• Instead of updating the average rate $\rho$ with a simple arithmetic EMA or a ratio of EMAs, it introduces an Exponential Moving Harmonic Mean.
• The algorithm tracks the reciprocals of the rates ($r/\tau$) for positive and negative rewards separately, performs exponential moving averages of these reciprocals and their associated weights, and then inverts them to calculate the current estimate of $\rho$.

3. Main Contributions

1. Theoretical Analysis of Existing Algorithms: The work formally shows (via Theorem 1) that the ratio of arithmetic means (used by Relaxed-SMART) corresponds to the harmonic mean only if the covariance between rewards and the ratio of time to reward is zero. In non-stationary or dependent settings, this leads to an incorrect rate estimation.
2. Novel Operator: The introduction of the modified harmonic mean operator ($\mathcal{H}$), which is robust against zero and mixed-sign rewards while maintaining mathematical correctness for averaging rates.
3. Algorithmic Generalization: The development of Harmonic R-Learning, a model-free algorithm that generalizes existing R-Learning variants to SMDPs without the stationarity or independence assumptions of SMART and Relaxed-SMART.
4. Axiomatic Proofs: Proofs establishing that $\mathcal{H}$ is a general mean but not a quasi-arithmetic mean, thereby clarifying its mathematical standing relative to traditional means.

4. Empirical Results

The authors evaluated Harmonic R-Learning against SMART and Relaxed-SMART in two domains:

• Synthetic Two-State SMDP:

  • Setup: A continuous task with two actions. Action A had independent rewards and durations. Action B had dependent, non-stationary rewards and durations (using drifting sine/cosine functions with logarithmization).
  • Result: In settings where the dependency between reward and duration made the "true" optimal action (Action B) difficult to identify within the learning horizon, SMART and Relaxed-SMART failed (dropping to 0% success in more difficult settings). Harmonic R-Learning maintained a high success rate across all parameter combinations and demonstrated superior robustness to non-stationarity and dependency.

• Bitcoin Trading (Real-World Data):

  • Setup: A highly volatile, non-stationary environment using minute-level Bitcoin price data (2012–2025). The task involved buying/selling with stochastic action durations (5–45 seconds). Two versions were tested: one with random durations (independent) and one where duration was scaled by reward magnitude (dependent).
  • Result:
    • In the independent version, all algorithms performed similarly, as expected by theory.
    • In the dependent version (where reward magnitude influenced duration), Harmonic R-Learning significantly outperformed both SMART and Relaxed-SMART, achieving a higher win rate across 21 data segments. This confirms the theoretical claim that the approximation via the ratio of means fails when rewards and durations are coupled.

5. Significance and Claims

The work claims that Harmonic R-Learning represents a necessary correction for RL with average reward in SMDPs where reward and duration distributions are non-stationary or dependent.

• It is argued that previous methods (SMART/Relaxed-SMART) are fundamentally flawed under these specific conditions because they rely on arithmetic approximations that ignore the coupling between reward magnitude and time.
• The modified harmonic mean operator is presented as the mathematically correct tool for averaging rates in RL, thereby extending the applicability of R-Learning to complex, real-world scenarios such as financial trading where such dependencies are common.
• The work is positioned as a theoretical and empirical improvement over the state of the art for model-free optimization of average reward in semi-Markov settings, specifically addressing the gaps of "non-stationary" and "dependent" in the current literature.