PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Fair Policies in Multiobjective (Deep) Reinforcement Learning with Average and Discounted Rewards

Umer Siddique, Paul Weng, Matthieu Zimmer

arXiv:2008.07773v1cs.AIcs.LG

TL;DR

When autonomous systems affect multiple users, aggregate-utility objectives can sacrifice some users’ utility, motivating fair RL policies. The paper formulates fair optimization, analyzes discounted and average rewards, and adapts deep RL algorithms. Its theoretical results establish stationary-policy solutions for the discounted and GGF-average problems; the cited bound has restrictive conditions.

  • Problem

    Aggregate-utility objectives can sacrifice some users’ utility when autonomous systems affect multiple users, motivating policies that treat users equitably.

    Source: §1 · p. 1

  • Method

    The paper formulates fair optimization in RL and adapts three deep RL algorithms to optimize a fair welfare function.

    Source: §1 · p. 1

  • Results

    The discounted problem admits a stationary stochastic Markov solution, and the GGF-average problem admits one with constant gain in weakly communicating MOMDPs.

    Source: §3.1 · pp. 4–5

  • Takeaways & Limitations

    The paper concludes that adaptations of three deep RL algorithms can solve large-scale fair optimization problems, with empirical validation across three domains.

    Source: §7 · p. 9

    The approximation-error bound applies only when Pπ∗1 has n distinct eigenvalues and may be difficult to interpret or evaluate because it involves an eigenvector-matrix condition number.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

As the operations of autonomous systems generally affect simultaneously several users, it is crucial that their designs account for fairness considerations. In contrast to standard (deep) reinforcement learning (RL), we investigate the problem of learning a policy that treats its users equitably. In this paper, we formulate this novel RL problem, in which an objective function, which encodes a notion of fairness that we formally define, is optimized. For this problem, we provide a theoretical discussion where we examine the case of discounted rewards and that of average rewards. During this analysis, we notably derive a new result in the standard RL setting, which is of independent interest: it states a novel bound on the approximation error with respect to the optimal average reward of that of a policy optimal for the discounted reward. Since learning with discounted rewards is generally easier, this discussion further justifies finding a fair policy for the average reward by learning a fair policy for the discounted reward. Thus, we describe how several classic deep RL algorithms can be adapted to our fair optimization problem, and we validate our approach with extensive experiments in three different domains.

1. Introduction

The paper addresses how autonomous systems can treat multiple affected users equitably, since maximizing aggregate utility can sacrifice some users’ utility. It formulates fair optimization in reinforcement learning, studies discounted and average rewards, adapts deep RL algorithms, and evaluates the approach in three domains.

1. Introduction

  • Aggregate-utility optimization can sacrifice some users’ utility, so fairness matters when autonomous systems affect multiple users.The paper contrasts this with maxmin fairness, which may fail to be strictly efficient for all users because it focuses on one user.Source: §1 · p. 1
  • The paper uses the generalized Gini social welfare function to encode fairness through efficiency, impartiality, and equity.Source: §1 · p. 1
  • The authors formulate fair optimization in RL and analyze stationary Markov policies, state-dependency, and discounted-to-average reward approximation error.Source: §1 · p. 1
  • They adapt three deep RL algorithms to the fair optimization problem and report extensive experiments in three domains.Source: §1 · p. 2

2. Background

The background introduces MDPs and their discounted and average reward criteria, then extends them to vector-valued rewards for multiple objectives or users. It motivates the generalized Gini function as a way to encode balanced, fair solutions.

2.1. Markov Decision Processes

  • MDPs model states, actions, transitions, rewards, and initial-state distributions; policies select actions, and standard deep RL methods commonly target discounted rewards.Discounted value sums future rewards with a discount factor, while average reward captures long-run performance; the criteria are connected through occupation distributions.Source: §2.1 · pp. 2–3

2.2. Multiobjective Markov Decision Process

  • MOMDPs use vector rewards to represent multiple criteria or users, and optimization seeks Pareto-optimal policies, although their number may be exponentially large.Weighted sums offer one solution but do not control how balanced the objective values are; nonlinear aggregation is proposed as a better fit for balanced solutions.Source: §2.2 · p. 3

2.3. Generalized Gini Social Welfare Function

  • Fair solutions are required to be efficient, impartial, and equitable: Pareto-optimal, equal-treatment-of-equals, and responsive to Pigou-Dalton transfers.The paper assumes objectives are equal and should be treated alike.Source: §2.3 · pp. 3–4
  • The generalized Gini function sorts utilities from lowest to highest and applies positive, strictly decreasing weights, yielding a piecewise-linear concave welfare function.Its weights can recover maxmin, regularized maxmin, utilitarian, and leximin objectives; its properties support efficiency, impartiality, and equity.Source: §2.3 · p. 4

3. Fair Policies in RL

The paper formulates fair RL as selecting a policy that generates a fair reward distribution across fixed users, using discounted or average rewards. Its theoretical analysis addresses policy sufficiency, state dependence, and discounted-to-average approximation error.

3. Fair Policies in RL

  • Fair optimization in RL selects a policy that generates a fair distribution of rewards to D fixed users, with the objective defined using discounted or average rewards.The paper calls the two formulations GGF-γ and GGF-average problems.Source: §3 · p. 4

3.1. Theoretical Discussions

  • A stationary stochastic Markov policy suffices for an optimal solution, reducing the search to that policy class; deterministic policies may not be optimal for fairness.The stationary-policy result holds for any monotonic objective function, not only GGF.Source: §3.1 · pp. 4–5
  • Discounted GGF optimality can depend on the initial state: the example’s policy chooses Up at both s1 and s2 from s1, but Down at s2 is preferred when starting from s2.For average rewards, optimal preferences remain state-independent because the optimal policy’s gain is constant.Source: §3.1 · p. 5
  • The GGF-average problem in a weakly communicating MOMDP admits an optimal stationary stochastic Markov policy with constant gain.Source: §3.1 · p. 5
  • For weakly communicating MOMDPs, the paper establishes a GGF approximation-error bound for discounted-optimal versus average-optimal policies when γ is sufficiently close to 1.The bound’s error tends to zero as γ approaches 1 and depends mainly on the spectral radius of the Drazin inverse, interpretable as a measure of time spent in transient states.Source: §3.1 · p. 5
  • Applied to single-objective weakly communicating MDPs, the new theorem yields an alternative approximation-error bound that is more general than Theorem 3.4.Source: §3.1 · p. 5

4. Algorithms

The paper adapts deep RL algorithms to optimize fair objectives using discounted rewards, which can also provide approximate average-reward solutions when γ is close enough to 1. Its DQN and policy-gradient variants differ in the objective they optimize and their support for stochastic policies.

4. Algorithms

  • Discounted-reward adaptations can provide approximate solutions to the average-reward problem when γ is close enough to 1.Source: §4 · p. 6

DQN

  • The adapted DQN predicts a multiobjective Q function, but optimizes an expectation of GGF rather than GGF of an expectation, yielding a lower bound on the intended objective.Directly predicting GGF values would prevent bootstrapping.Source: §4 · p. 6

Policy Gradient Methods

  • Policy-gradient methods directly optimize the desired GGF objective and can learn stochastic policies that may strictly dominate deterministic ones.Source: §4 · p. 6
  • The paper applies the GGF policy-gradient method to PPO and A2C, naming the resulting algorithms GGF-PPO and GGF-A2C.Initial states are stored to estimate J(πθ) for sorting the weights, using the critic’s value approximation.Source: §4 · p. 6

5. Experimental Results

The experiments compare standard RL with GGF-adapted algorithms in species conservation, traffic-light control, and data-center control. Across these domains, the reported GGF scores or inequality measures favor GGF adaptations, while standard algorithms often achieve better average objectives.

5. Experimental Results

  • Standard algorithms performed better on average accumulated densities in SC and average waiting times in TL, whereas GGF optimization trades average performance for equity.In TL, all RL algorithms beat the fixed policy after training, and the fixed policy outperformed the random policy.Source: §5 · pp. 7–8, Figure 2 · p. 7, Figure 6 · p. 8
  • In SC, all three GGF algorithms achieved higher testing GGF scores than their original algorithms.The score is computed from sample-average vector rewards over 50 test runs; the figure compares DQN, A2C, PPO, and their GGF versions.Source: §5 · p. 7, Figure 3 · p. 7
  • In SC, standard algorithms produced higher total accumulated densities, but their two species’ individual densities were more unequal than those from GGF algorithms.The individual-density plots show the two species’ testing densities.Source: §5 · p. 7, Figure 4 · p. 7
  • In SC, every GGF algorithm had lower CV and higher minimum density than the standard algorithms.CV is presented as a simple inequality measure; Figure 5 reports CV and minimum and maximum densities.Source: §5 · p. 7, Figure 5 · p. 8
  • In TL, all three GGF algorithms scored better than their original counterparts, and GGF-PPO achieved the best score.GGF-DQN also outperformed the fixed policy; Figure 7 includes PPO and GGF-PPO results for two discount factors.Source: §5 · p. 8, Figure 7 · p. 8
  • In TL, GGF algorithms always had lower CV than their standard counterparts, while GGF-PPO had more balanced road-level waiting times.PPO had the lowest waiting time among the algorithms.Source: §5 · p. 8, Figure 8 · p. 8
  • With γ = 0.99999, GGF-PPO’s TL score was very similar to its γ = 0.99 result, suggesting a policy close to GGF-average optimality.The authors suggest that γ = 0.99 is sufficient in practice except for difficult MDP structures.Source: §5 · pp. 8–9, Figure 7 · p. 8
  • In DC, GGF-A2C and GGF-PPO had higher GGF scores than their original algorithms and lower CV than those algorithms.The continuous-state-and-action domain was tested with A2C and PPO; the bandwidth figure reports CV and minimum and maximum bandwidths.Source: §5 · p. 9, Figure 9 · p. 9

6. Related Work

Prior fair-optimization work often assumes a known model, while related sequential-decision studies address different settings or objectives. The paper positions its contribution as fair optimization in RL, including large or continuous state spaces.

6. Related Work

  • Fair optimization is an active area spanning applied mathematics, operations research, and theoretical computer science.Classic continuous and combinatorial optimization problems have been extended to incorporate fairness.Source: §6 · p. 9
  • Many prior optimization methods assume the full model is known; Ogryczak et al. (2013) solve the discounted problem by linear programming under that condition.This paper instead addresses RL with discounted and average rewards, including large or continuous state spaces.Source: §6 · p. 9
  • Related sequential work includes fair multi-armed bandits and decentralized multi-agent RL, while Cheung (2019) studies regret minimization in tabular UCRL.The cited multi-agent work uses a different welfare function; Cheung (2019) also studies non-stationary deterministic policies, unlike this paper.Source: §6 · p. 9

7. Conclusion

The conclusion recaps the introduction of fair optimization in RL, its theoretical discussion, adapted deep RL algorithms, and empirical validation.

7. Conclusion

  • The paper introduces fair optimization in RL, discusses it theoretically, adapts three deep RL algorithms, and validates them empirically.The authors identify other fair welfare functions, distributed control, and direct adaptation for average rewards as possible future work.Source: §7 · p. 9

A. Proofs of Theoretical Discussion

The proofs establish stationary-policy results for discounted and average rewards, including a constant-gain solution for the GGF-average problem in weakly communicating MOMDPs.

A. Proofs of Theoretical Discussion

  • Theorem A.5 gives a discounted-value/gain relation for stationary policies when γ exceeds a threshold involving the spectral radius of H P^π.H P^π is identified as the Drazin inverse of I − P^π.Source: A. Proofs of Theoretical Discussion · p. 12
  • For any MOMDP, the discounted-reward GGF problem admits a solution that is a stationary stochastic Markov policy.The proof uses the fact that discounted occupation distributions, and therefore policy GGF evaluations, can be matched by stationary stochastic Markov policies.Source: A. Proofs of Theoretical Discussion · p. 12
  • The Pareto-optimal gains can be obtained using only stationary policies.The cited result states that a stationary policy can match or exceed a policy's discounted value after scaling by 1 − γ when γ is close to one.Source: A. Proofs of Theoretical Discussion · p. 12
  • For any weakly communicating MOMDP, the GGF-average problem admits a stationary stochastic Markov solution with constant gain.The proof constructs a policy with one closed recurrent class and transient states outside it.Source: A. Proofs of Theoretical Discussion · pp. 12–13

B. Descriptions of Experimental Domains

The appendix describes species-conservation and traffic-light domains as multiobjective control problems, representing their users' outcomes with separate reward components.

B.1. Conservation of two endangered species

  • The species-conservation domain models interventions affecting endangered sea otters and northern abalones, with the aim of maintaining their populations at relatively balanced levels.The environment is partially observable but is solved as an MOMDP; its two reward components represent the species and do not depend on actions.Source: §B.1 · pp. 14–15
  • The species model considers five management actions, including doing nothing, introducing otters, and applying abalone or otter controls.The state includes sea-otter population, abalone age-group populations, and abalone survival rates.Source: §B.1 · p. 14

B.2. Traffic Light Control

  • The traffic-light domain evaluates waiting times for four directions separately, rather than averaging waiting times across all lanes as in the usual approach.It simulates a single eight-lane SUMO intersection with four traffic-light phases.Source: §B.2 · p. 15, Figure 11 · p. 15
  • The traffic-light state records the current phase and each lane's waiting time and stopped-car density, while actions select a phase.Each phase has fixed duration, and new vehicles enter each lane according to a fixed Bernoulli distribution per episode.Source: §B.2 · p. 15

B.3. Data Center Traffic Control

The data-center domain applies fair multiobjective control to host bandwidths while penalizing queue lengths; the appendix also lists training hyperparameters and additional experimental results.

B.3. Data Center Traffic Control

  • The data-center controller seeks to maximize each host's bandwidth separately while penalizing queue lengths and ensuring fairness.The experiment uses a fat-tree network with 16 hosts, 20 switches, and 80 queues.Source: §B.3 · p. 16, Figure 13 · p. 16

D. Additional Experimental Results

D.1. Conservation of two endangered species

With faster-decaying GGF weights, adapted algorithms produce more balanced conservation outcomes. In traffic control, GGF policies improve fairness across directions, with a waiting-time trade-off when traffic changes during the day.

D.1. Conservation of two endangered species

  • The SC weight analysis compares GGF coefficients decreasing as 1/10^i with the previously used 1/2^i weights.The authors report similar conclusions for both weight settings.Source: §D.1 · p. 18
  • GGF-DQN, GGF-A2C, and GGF-PPO achieve higher GGF scores and more balanced densities than their standard counterparts.The reported score comparison uses faster-decaying weights; Figure 15 shows the density distributions.Source: §D.1 · p. 18, Figure 14 · p. 18, Figure 15 · p. 18
  • With faster-decaying weights, the GGF algorithms have lower CVs and produce more balanced objective distributions than standard RL algorithms.The comparison also considers minimum and maximum densities.Source: §D.1 · p. 18, Figure 16 · p. 18

D.2. Traffic Light Control

D.3. Data Center Traffic Control

In data-center traffic control, PPO and its GGF version converge to higher episodic rewards than fixed and random policies. The GGF algorithms trade lower average bandwidth for more equal allocation while still outperforming those baselines.

D.3. Data Center Traffic Control

  • PPO and GGF-PPO converge to much higher episodic rewards than fixed and random policies.Figure 23 reports learning curves over 20 runs with different seeds.Source: Figure 23 · p. 21, §D.3 · p. 21
  • GGF-PPO and GGF-A2C achieve lower average bandwidth than PPO and A2C while allocating bandwidth more equally across hosts.The authors attribute the lower average bandwidth to the difficulty of maximizing rewards while ensuring fairness.Source: §D.3 · p. 21
  • The data-center comparison uses a fixed policy that always selects maximum bandwidth per host and a random policy with uniform action selection.Source: §D.3 · p. 21

Related papers

Loading 2008.07773v1…