When modifying existing policies in high-risk settings, it is often necessary to ensure with high certainty that the newly proposed policy improves upon a baseline, such as the status quo. In this work, we consider the problem of safe policy improvement, where one only adopts a new policy if it is deemed to be better than the specified baseline with at least a pre-specified probability. We focus on threshold policies, a ubiquitous class of policies with applications in economics, healthcare, and digital advertising. Existing methods rely on potentially underpowered safety checks and limit the opportunities for finding safe improvements, so too often they must revert to the baseline to maintain safety. We overcome these issues by leveraging the most powerful safety test in the asymptotic regime and allowing for multiple candidates to be tested for improvement over the baseline. We show that in adversarial settings, our approach controls the rate of adopting a policy worse than the baseline to the pre-specified error level, even in moderate sample sizes. We present CSPI and CSPI-MT, two novel algorithms for selecting cutoff(s) to maximize the policy improvement from baseline. We demonstrate through both synthetic and external datasets that our approaches improve both the detection rates of safe policies and the realized improvement, particularly under stringent safety requirements and low signal-to-noise conditions.

Recommender systems in social media websites provide value to their communities by recommending engaging content and meaningful connections. Scaling high-quality recommendations to billions of users in real-time requires sophisticated ranking models operating on a vast number of potential items to recommend, becoming prohibitively expensive computationally. A common technique "funnels'' these items through progressively complex models ("multi-stage''), each ranking fewer items but at higher computational cost for greater accuracy. This architecture introduces a trade-off between the cost of ranking items and providing users with the best recommendations. A key observation we make in this paper is that, all else equal, ranking more items indeed improves the overall objective but has diminishing returns. Following this observation, we provide a rigorous formulation through the framework of DR-submodularity, and argue that for a certain class of objectives (reward functions), it is possible to improve the trade-off between performance and computational cost in multi-stage ranking systems with strong theoretical guarantees. We show that this class of reward functions that provide this guarantee is large and robust to various noise models. Finally, we describe extensive experimentation of our method on three real-world recommender systems in Facebook, achieving 8.8% reduction in overall compute resources with no significant impact on recommendation quality, compared to a 0.8% quality loss in a non-personalized budget allocation.

Social media platforms like Facebook and YouTube connect people with communities that reflect their own values and experiences. People discover new communities either organically or through algorithmic recommendations based on their interests and preferences. We study online journeys users take through these communities, focusing particularly on ones that may lead to problematic outcomes. In particular, we propose and explore the concept of gateways, namely, entities associated with a higher likelihood of subsequent engagement with problematic content. We show, via a real-world application on Facebook groups, that a simple definition of gateway entities can be leveraged to reduce exposure to problematic content by 1% without any adverse impact on user engagement metrics. Motivated by this finding, we propose several formal definitions of gateways, via both frequentist and survival analysis methods, and evaluate their efficacy in predicting user behavior through offline experiments. Frequentist, duration-insensitive methods predict future harmful engagements with an 0.64–0.83 AUC, while survival analysis methods improve this to 0.72–0.90 AUC.

This paper explores the power of failure detectors in read write shared memory systems with n processes whose names are drawn from the set {1...m}, m>=2n-1. We do so by making an additional assumption, name obliviousness, on top of the three failure detector assumptions introduced by ZieliDski. We present name non-oblivious failure detectors that are strong enough to wait-free solve the Symmetry Breaking (SB) problem, but not enough to solve the (n-1)-Set Consensus problem. Furthermore a family of weakest such failure detectors is presented. On the other hand we show that any non trivial name oblivious failure detector can wait-free solve (n-1)-Set Consensus, by introducing a simple extension to anti-Omega, the Loose-anti-Omega failure detector, and proving that it is the weakest failure detector that conforms to the four assumptions above.