Timezone: »

 
Poster
Envy-free Policy Teaching to Multiple Agents
Jiarui Gan · R Majumdar · Adish Singla · Goran Radanovic

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #532
in Poster Session 6 »

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.

Keywords: Fairness · envy-freeness · price of fairness · policy teaching · reward design

Author Information

Jiarui Gan (University of Oxford)
R Majumdar (MPI-SWS)
Adish Singla (MPI-SWS)
Goran Radanovic (Max Planck Institute for Software Systems)

More from the Same Authors