The Offset Tree for Learning with Partial Labels

2008/12/21 by Alina Beygelzimer, John Langford, Beygelzimer, Alina +1 · 6 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.0812.4044

openalex publication_date 2008/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 of 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(log₂ 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.

Citations

• A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting

Cited by

• Hour-Aware Adaptive Risk Management for Autonomous Memecoin Trading on Solana DEXs: Evidence, Theory, and Design Lessons from a 15-Day Deployment
• APRIL: Annotations for Policy evaluation with Reliable Inference from LLMs
• GrowthHacker: Automated Off-Policy Evaluation Optimization Using Code-Modifying LLM Agents
• Group-Sensitive Offline Contextual Bandits
• PERRY: Policy Evaluation with Confidence Intervals using Auxiliary Data
• Exploitation Over Exploration: Unmasking the Bias in Linear Bandit Recommender Offline Evaluation

Related

• Harnessing the Power of Choices in Decision Tree Learning
• Learning to Abstain from Binary Prediction
• Optimal Sparse Decision Trees
• Partial-Label Learning with a Reject Option
• Learning invariants using decision trees and implication counterexamples