Envy-free Policy Teaching to Multiple Agents

Jiarui Gan, Rupak Majumdar, Adish Singla, Goran RadanovicNeurIPS 2022 · OpenReview

Introduction

In reinforcement learning, "policy teaching" involves modifying an agent's reward function to incentivize a specific target behavior. This technique has broad applications, from educational software that encourages students to practice weak skills to safety protocols that penalize dangerous actions.

However, real-world applications often involve multiple, heterogeneous agents. These agents may have different innate preferences, skill levels, and discount rates (how much they value immediate versus future rewards). When a teacher provides personalized incentives to guide this diverse group toward a common goal, a significant challenge arises: fairness. If one agent receives a lucrative bonus for completing a task while another receives nothing, the uncompensated agent may experience "envy."

The Fairness Dilemma

The core problem lies in designing incentive programs that are both feasible (they successfully teach the target policy) and envy-free (no agent prefers another's incentive package over their own).

The core fairness dilemma: When agents require different incentives to follow a target policy, personalized adjustments can lead to perceived unfairness.

To tackle this, researchers have adapted the concept of Envy-Freeness (EF) from the fair division literature, applying it to Markov Decision Processes (MDPs). The framework defines three hierarchical levels of fairness:

  1. Weak Envy-Freeness (WEF): No agent prefers another's adjustment assuming both strictly follow the target policy.
  2. Envy-Freeness (EF): No agent prefers another's adjustment, even if they were to deviate from the target policy to maximize their own reward under the new adjustment.
  3. Strong Envy-Freeness (SEF): All agents receive the exact same, universal incentive program.

Key Insights: Penalties, Rewards, and Efficiency

By formulating the search for a minimum-cost fair adjustment as a convex optimization problem, the authors demonstrate that the set of fair and feasible solutions forms a convex polytope. This allows for efficient, polynomial-time computation of fair teaching policies.

However, the existence of these solutions depends heavily on the tools available to the teacher:

  • The Power of Penalties: If the teacher is allowed to use penalties (negative rewards), an envy-free solution is always guaranteed. By heavily penalizing non-target actions universally, the teacher can make the target policy optimal and fair for everyone.
  • Reward-Only Limitations: If the teacher is restricted to providing only bonuses (non-negative adjustments), a fair solution might not exist if agents have different discount factors.
A counter-example MDP demonstrating that a fair, non-negative adjustment scheme may not exist when agents have differing discount factors.

The Price of Fairness

Incorporating fairness constraints naturally increases the cost of the teaching program. The paper quantifies this "Price of Fairness" (PoF)—the ratio of the cost of the optimal fair program to the cost of the optimal unfair program.

The authors provide tight asymptotic bounds on the PoF across different scenarios:

Scenario PoWEF PoEF PoSEF
No restriction $\Theta(\lambda \cdot \sqrt{m})$ $\Theta(\lambda \cdot n \cdot \sqrt{m})$ $\Theta(\lambda \cdot n \cdot \sqrt{m})$
Non-neg & identical $\gamma$ $\Theta(\lambda \cdot n \cdot \sqrt{m})$ $\Theta(\lambda^2 \cdot n \cdot \sqrt{m})$ $\Theta(\lambda^2 \cdot n \cdot \sqrt{m})$

(Note: $n$ is the number of agents, $m$ is the number of state-action pairs, and $\lambda$ is the geometric sum of the discount factor.)

Crucially, these results show that the cost of fairness increases at most quadratically with the MDP's horizon and linearly with the number of agents. This suggests that the overhead for ensuring fairness is mathematically manageable and scales predictably.

Limitations and Future Directions

While this framework provides a strong theoretical foundation, it assumes agents operate independently without interacting or competing for resources. Future research could explore multi-agent environments where agents influence each other's state transitions.

Additionally, the current model measures cost based on the norm of the reward modification; exploring other metrics, such as the total cumulative payment made by the teacher, could yield new insights. Finally, it is worth noting that these EF notions apply only to the teacher's adjustments. If the underlying task or innate reward structure is inherently inequitable, these adjustments alone may not satisfy broader societal definitions of fairness.

Summary updated

Abstract

We study envy-free policy teaching. A number of agents independently explore a common Markov decision process (MDP), but each with their own reward function and discounting rate. A teacher wants to teach a target policy to this diverse group of agents, by means of modifying the agents' reward functions: providing additional bonuses to certain actions, or penalizing them. When personalized reward modification programs are used, an important question is how to design the programs so that the agents think they are treated fairly. We adopt the notion of envy-freeness (EF) from the literature on fair division to formalize this problem and investigate several fundamental questions about the existence of EF solutions in our setting, the computation of cost-minimizing solutions, as well as the price of fairness (PoF), which measures the increase of cost due to the consideration of fairness. We show that 1) an EF solution may not exist if penalties are not allowed in the modifications, but otherwise always exists. 2) Computing a cost-minimizing EF solution can be formulated as convex optimization and hence solved efficiently. 3) The PoF increases but at most quadratically with the geometric sum of the discount factor, and at most linearly with the size of the MDP and the number of agents involved; we present tight asymptotic bounds on the PoF. These results indicate that fairness can be incorporated in multi-agent teaching without significant computational or PoF burdens.
BibTeX
@inproceedings{gan2022envy,
  author = {Jiarui Gan and Rupak Majumdar and Adish Singla and Goran Radanovic},
  title = {{Envy-free Policy Teaching to Multiple Agents}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=nfNFyOAJYH},
}

Loading related content...

Figure