State-Visitation Fairness in Average-Reward MDPs
  Fairness has emerged as an important concern in automated decision-making in
recent years, especially when these decisions affect human welfare. In this
work, we study fairness in temporally extended decision-making settings,
specifically those formulated as Markov Decision Processes (MDPs). Our proposed
notion of fairness ensures that each state's long-term visitation frequency is
more than a specified fraction. In an average-reward MDP (AMDP) setting, we
formulate the problem as a bilinear saddle point program and, for a generative
model, solve it using a Stochastic Mirror Descent (SMD) based algorithm. The
proposed solution guarantees a simultaneous approximation on the expected
average-reward and the long-term state-visitation frequency. We validate our
theoretical results with experiments on synthetic data.
