The offset tree for learning with partial labels

By Alina Beygelzimer, J. Langford. 2008

201 citations recorded by the source corpus.

We present an algorithm, called the Offset Tree, for learning to make decisions in situations where the payoff of only one choice is observed, rather than all choices. The algorithm reduces this setting to binary classification, allowing one to reuse any existing, fully supervised binary classification algorithm in this partial information setting. We show that the Offset Tree is an optimal reduction to binary classification. In particular, it has regret at most (k-1) times the regret of the binary classifier it uses (where k is the number of choices), and no reduction to binary classification can do better. This reduction is also computationally optimal, both at training and test time, requiring just O(log2 k) work to train on an example or make a prediction. Experiments with the Offset Tree show that it generally performs better than several alternative approaches.

Subfields: Artificial Intelligence, Management Science and Operations Research, Representation & Self-Supervised Learning

How researchers see this paper

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

In Artificial Intelligence

In Management Science and Operations Research

In Representation & Self-Supervised Learning

Citations in the corpus

Balanced Policy Evaluation and Learning (2017, methodology): “Unlike [1, 7, 13, 41, 45], our (nonconvex) policy optimization problem does not reduce to weighted classification precisely because our weights are not multiplies of ⇡Ti(Xi) (but therefore our weights also lead to better performance).”
Generalized random forests (2016, background): “(2009) for treatment effect estimation, Beygelzimer and Langford (2009) and Kallus (2016) for personalized policy allocation, and Ciampi et al. (1986), Gordon and Olshen (1985), LeBlanc and Crowley (1992), Molinaro et al.”
The Econometrics of Randomized Experiments (2016, background): “Bloom (1984), Zelen (1979, 1990), Baker and Lindeman (1994), Cuzick, Edwards, and Segnan (1997), contain early and independent discussions of the instrumental variables approach, some in the special case of one-sided non-compliance, and Imbens and Angrist (1994), Angrist, Imbens and Rubin (1996) dev”
The State of Applied Econometrics - Causality and Policy Evaluation (2016, neutral): “A literature in machine learning considers this problem ([Beygelzimer and Langford, 2009]; [Dud́ık et al., 2011]); some open questions include the ability to obtain confidence intervals on differences between policies obtained from these methods.”
Doubly Robust Policy Evaluation and Optimization (2014, methodology): “The numbers reported here are not identical to those by Beygelzimer and Langford (2009), even though we used a similar protocol on the same datasets, probably because of small diﬀerences in the data structures used.”
Counterfactual Estimation and Optimization of Click Metrics for Search Engines (2014, neutral): “Another direction worth investigating is direct optimization of policies based on exploration data with, for instance, the offset tree algorithm [4].”
Doubly Robust Policy Evaluation and Learning (2011, methodology): “…problem with this method is that the estimate ˆ ̺ is formed without the knowledge of π and hence might focus on approximating ̺ mainly in the areas that are irrelevant for V π and not sufﬁciently in the areas that are important for V π ; see Beygelzimer & Langford (2009) for a more reﬁned analysis.”
Off-policy Bandits with Deficient Support (2020, methodology): “To simulate bandit feedback for the CIFAR10 dataset, our experiment setup follows traditional supervised → bandit conversion for multi-class classification datasets [2].”
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits (2014, methodology): “The speciﬁc CSC oracle we use is a reduction to squared-loss regression (Algorithms 4 and 5 of Beygelzimer and Langford (2009)) which is amenable to online updates.”
Policy Evaluation and Optimization with Continuous Treatments (2018, background): “IPW is unbiased, with a slower rate of convergence dependent on the number of treatments [3], and it is optimal in the sense of minimax eﬃciency when no additional information about the reward structure is available [24].”
Causal Falling Rule Lists (2015, methodology): “Methods have used tree structures (Su, Kang, and Levine 2012; Su and Nickerson 2009; Athey and Imbens 2015; Beygelzimer and Langford 2009) to form such treatment effect subgroups.”
Efficient Policy Learning (2017, methodology): “Following an extensive existing literature (Beygelzimer and Langford, 2009; Bottou et al., 2013; Chen et al., 2016; Dud́ık et al., 2011; Kitagawa and Tetenov, 2015; Swaminathan and Joachims, 2015; Zhao et al., 2012; Zhou et al., 2015), we focus on learners π̂ obtained by optimizing a policy value…”
Online Evaluation for Information Retrieval (2016, unknown): “Such an approach, as taken by some previous work [Beygelzimer and Langford, 2009, Strehl et al., 2011], ignores estimation variance, and therefore does not always produce near-optimal policies reliably. Recently, Swaminathan and Joachims [2015a] propose to use estimation variance as a regularization”
Confounding-Robust Policy Improvement (2018, methodology): “We generalize the class of IPW-based estimators and construct uncertainty sets centered at the nominal IPW weights that can be calibrated by approaches for sensitivity analysis in causal inference.”
CAB: Continuous Adaptive Blending for Policy Evaluation and Learning (2019, methodology): “This enables Empirical Risk Minimization (ERM) for batch learning from bandit feedback (BLBF) (Zadrozny et al., 2003; Beygelzimer & Langford, 2009; Strehl et al., 2011; Swaminathan & Joachims, 2015a;b), where the algorithm ﬁnds the policy in Π that maximizes the estimated expected reward possibly…”
Bayesian Counterfactual Risk Minimization (2018, methodology): “Following prior work, we use a standard supervisedto-bandit conversion to simulate logged bandit feedback (Beygelzimer and Langford, 2009).”