Issues with Value-Based Multi-objective Reinforcement Learning: Value Function Interference and Overestimation Sensitivity

1. Problem Statement

Multi-objective Reinforcement Learning (MORL) extends standard RL to environments with multiple, conflicting objectives represented by vector-valued rewards. While value-based methods like Q-learning are widely adapted for MORL by learning vector-valued Q-functions and using a scalarization operator (utility function $U$) for action selection, this paper identifies two critical, previously unreported issues that hinder performance when non-linear utility functions are used:

1. Value Function Interference: The expected vector return learned by the agent (the mean of future returns) may not contain sufficient information to determine the optimal action under a non-linear utility function. Specifically, the utility of the expected vector ($U(E[Return])$) often differs from the expected utility of the returns ($E[U(Return)]$). This discrepancy leads to sub-optimal action selection, particularly for Expected Scalarised Return (ESR) optimization in stochastic environments, but also for Scalarised Expected Return (SER) in deterministic environments due to tie-breaking stochasticity.
2. Sensitivity to Overestimation: While Q-learning is known to suffer from overestimation bias in single-objective RL, this paper demonstrates that non-linear utility functions in MORL are significantly more sensitive to this bias. Even consistent overestimation can alter the preference ordering of actions, causing the agent to select sub-optimal policies, whereas linear scalarization remains robust to uniform overestimation.

2. Methodology

The authors employ a combination of theoretical analysis and empirical experimentation using a tabular Multi-objective Q-learning (MOQ) agent.

• Algorithmic Framework: They utilize a modified version of standard MOQ (Algorithm 1) that handles vector rewards and uses an augmented state space $(s, P, t)$, where $P$ is the accumulated return vector and $t$ is the time-step (necessary for non-linear utility and discounting).
• Optimization Criteria: The study distinguishes between:
  • SER (Scalarised Expected Return): Maximizing $U(E[Return])$.
  • ESR (Expected Scalarised Return): Maximizing $E[U(Return)]$.
• Experimental Setup:
  • Value Function Interference: Tested on simple Multi-objective Markov Decision Processes (MOMDPs) and Multi-objective Multi-Armed Bandits (MOMABs).
    • Stochastic Case: A single-state bandit with stochastic rewards to demonstrate ESR vs. SER divergence.
    • Deterministic Case: A three-state MOMDP where deterministic tie-breaking (random vs. fixed index) is manipulated to show how induced stochasticity causes interference.
  • Overestimation Sensitivity: Tested on the DST-Mixed grid-world environment (mapped to a MOMAB).
    • Three utility functions were compared: Linear Scalarization, Thresholded Lexicographic Ordering (TLO), and Chebyshev Distance.
    • Experiments involved adding controlled noise ($\delta$) to Q-values (both consistent and inconsistent) to simulate overestimation and measuring the frequency of incorrect policy selection and normalized regret.

3. Key Contributions

A. Identification of Value Function Interference

The paper formally defines Value Function Interference as the phenomenon where the learned vector Q-values (representing expected returns) fail to guide the agent to the optimal policy because the utility function is non-linear.

• Stochastic Environments: The agent learns $Q(s,a) = E[R]$. If $U$ is non-linear, $U(Q(s,a)) \neq E[U(R)]$. The agent optimizes the wrong objective (SER instead of ESR).
• Deterministic Environments: Even in deterministic settings, interference arises if the agent breaks ties between equally optimal actions randomly. This random tie-breaking introduces artificial stochasticity into the reward stream, causing the learned vector values for predecessor states to converge to a "mean" vector that yields a lower utility than the true optimal deterministic path.

B. Demonstration of Overestimation Sensitivity

The authors show that while linear scalarization is invariant to uniform overestimation (since $Q^* + \delta > Q + \delta$ preserves order), non-linear utility functions are not.

• TLO Sensitivity: Thresholded Lexicographic Ordering is extremely sensitive. A small overestimation can push a return vector across a utility threshold, causing a massive jump in perceived utility and leading to catastrophic policy errors.
• Chebyshev Sensitivity: While less sensitive than TLO, Chebyshev distance still suffers from preference reversals due to the non-linearity of the max operator.

C. Mitigation Strategies

• Deterministic Tie-Breaking: In deterministic MOMDPs, replacing random tie-breaking with a deterministic rule (e.g., always choosing the action with the lowest index) significantly reduces the frequency of convergence to sub-optimal policies, though it does not eliminate the problem entirely (especially if the greedy action changes frequently during learning).
• Proposed Future Directions: The authors suggest integrating Distributional RL (learning distributions over returns rather than just means) to correctly estimate ESR, or using Potential-Based Reward Shaping to scalarize returns at every time step (learning ESR directly), though the latter sacrifices the interpretability of vector Q-values.

4. Results

• Interference in Stochastic Settings: In the stochastic bandit experiment, standard MOQ with random tie-breaking converged to the sub-optimal arm in nearly 100% of trials for most learning rates, failing to learn the ESR-optimal policy.
• Interference in Deterministic Settings:
  • With random tie-breaking, the agent frequently converged to a sub-optimal policy (Policy 2) in the deterministic MOMDP, particularly with moderate learning rates ($\alpha \approx 0.5$).
  • With deterministic tie-breaking (low-index or high-index), the convergence to the sub-optimal policy dropped significantly (by ~30% in total trials), proving that the stochasticity of the tie-breaking mechanism is a primary driver of interference.
• Overestimation Impact:
  • Linear: Zero impact on policy selection regardless of overestimation magnitude.
  • TLO: Highly sensitive. Even minimal overestimation ($\delta=0.1$) caused a sharp increase in incorrect policy choices and normalized regret.
  • Chebyshev: Moderate sensitivity. Performance degraded as overestimation increased, but was more robust than TLO.
  • Inconsistent Overestimation: Was found to be more disruptive than consistent overestimation across all utility functions, as it alters relative action preferences.

5. Significance

This paper provides crucial insights for the design and deployment of MORL algorithms:

1. Theoretical Limitation: It highlights a fundamental limitation of standard vector-based Q-learning: learning the mean vector return is insufficient for non-linear utility optimization. This challenges the assumption that vector Q-learning is a direct drop-in replacement for scalar Q-learning in MORL.
2. Practical Implications: It warns practitioners that using non-linear utility functions (common in safety-critical or fairness-aware applications) with standard Q-learning can lead to severe performance degradation due to interference and overestimation sensitivity.
3. Algorithmic Guidance: It suggests that simple modifications, such as deterministic tie-breaking, can mitigate some issues in deterministic settings, but points toward more advanced solutions like Distributional RL or scalarized reward shaping for robust ESR optimization.
4. Deep RL Relevance: The authors note that these issues are likely exacerbated in Deep MORL (e.g., DQN extensions) where function approximation introduces noise and frequent changes in greedy actions, making the system highly susceptible to value function interference.