Importance Sampling for Fair Policy Selection

By Shayan Doroudi, Philip S. Thomas, Emma Brunskill. 2017

50 citations recorded by the source corpus.

We consider the problem of off-policy policy selection in reinforcement learning: using historical data generated from running one policy to compare two or more policies. We show that approaches based on importance sampling can be unfair---they can select the worse of two policies more often than not. We then give an example that shows importance sampling is systematically unfair in a practically relevant setting; namely, we show that it unreasonably favors shorter trajectory lengths. We then present sufficient conditions to theoretically guarantee fairness. Finally, we provide a practical importance sampling-based estimator to help mitigate the unfairness due to varying trajectory lengths.

Subfields: Probabilistic & Bayesian Methods, AI Ethics, Fairness & Society

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

In AI Ethics, Fairness & Society

Citations in the corpus

Beyond Individual and Group Fairness (2020, background): “…and contextual bandits [Joseph et al., 2016, Gillen et al., 2018, Gupta and Kamble, 2019] and reinforcement learning [Jabbari et al., 2017, Doroudi et al., 2017, Wen et al., 2019, Zhang and Shah, 2014], human-classifier hybrid decision systems [Madras et al., 2018], or fair…”
Estimating Counterfactual Treatment Outcomes over Time Through Adversarially Balanced Representations (2020, background): “Off-policy evaluation in reinforcement learning: In reinforcement learning, a similar problem to ours is off-policy evaluation, which uses retrospective observational data, also known as logged bandit feedback (Hoiles & Van Der Schaar, 2016; P˘aduraru et al., 2013; Doroudi et al., 2017).”
Learning When-to-Treat Policies (2019, methodology): “Inverse-propensity type methods, including outcome-weighted learning and importance sampling, are transparent and simple to implement; however, they have sometimes been observed exhibit problematically high variance, especially in dynamic settings (see, e.g., Doroudi, Thomas, and Brunskill 2017).”
Benchmarks for Deep Off-Policy Evaluation (2021, methodology): “This is critical for several reasons, including providing high-conﬁdence guarantees prior to deployment (Thomas et al., 2015), and performing policy improvement and model selection (Bottou et al., 2013; Doroudi et al., 2017).”
Importance Sampling Policy Evaluation with an Estimated Behavior Policy (2018, neutral): “mal validation loss – that would lead to lower MSE with RIS, however, to date we have not found one. Note that OIS also tends to under-estimate policy value in MDPs as has been previously analyzed by Doroudi et al. (2017). Appendix F shows the same observations in the HalfCheetah domain. Importance ”
Reliable Decision Support using Counterfactual Models (2017, background): “In RL, a related problem known as off-policy evaluation also uses retrospective observational data (see e.g., Dudík et al. 2011, Swaminathan and Joachims 2015, Jiang and Li 2016, Păduraru et al. 2012, Doroudi et al. 2017).”
Optimizing Long-term Social Welfare in Recommender Systems: A Constrained Matching Approach (2020, methodology): “Several methods for improved fairness in sequential decision-making have been proposed, including work on bandits (Joseph et al., 2016), RL (Jab-bari et al., 2017), and importance sampling (Doroudi et al., 2017).”
Policy Optimization via Importance Sampling (2018, methodology): “A more theoretically grounded analysis has been provided for policy selection [10], model-free [55] and model-based [53] policy evaluation (also accounting for samples collected with multiple behavioral policies), and combined with options [14].”
Behaviour Policy Estimation in Off-Policy Policy Evaluation: Calibration Matters (2018, methodology): “…weight (Precup, 2000), , we can form the stepwise Weighted Importance Sampling (WIS) estimator of V π e : In this work, we consider using the Per-Horizon WIS (PHWIS) estimator, which can handle differing trajectory lengths (Doroudi et al., 2017), to evaluate medical treatment strategies for sepsis.”
Fair Generative Modeling via Weak Supervision (2019, methodology): “For reinforcement learning, [44] used an importance sampling approach for selecting fair policies.”
Offline Policy Selection under Uncertainty (2020, background): “Oﬄine policy selection has also been studied by Doroudi et al. (2017), which considers what properties a point estimator should have in order for it to yield good rankings in terms of a notion of ranking score referred to as fairness .”