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).
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:
- Weak Envy-Freeness (WEF): No agent prefers another's adjustment assuming both strictly follow the target policy.
- 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.
- 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.
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