This research paper, authored by Khaled Eldowa and Pierre Gaillard, explores a middle ground in the world of online learning: the "two-point feedback" model. By allowing a learner to probe two actions instead of one, the authors demonstrate that we can achieve significantly better performance—sometimes matching the "gold standard" of full-information settings—even when dealing with complex, non-convex, and non-parametric problems.
TL;DR
The paper introduces a new algorithm for contextual bandits that uses two-point feedback to minimize regret in non-convex, non-parametric settings. By querying the difference between two actions, the algorithm achieves a $\sqrt{T}$ regret rate in low-dimensional or highly smooth scenarios, effectively closing the gap between limited bandit feedback and full-information learning.
What Problem Does This Paper Address?
In the standard contextual bandit problem, a decision-maker sees a context (like a user's profile), picks an action (like an ad), and sees the resulting loss. The goal is to perform as well as the best possible "policy" (a rule mapping contexts to actions).
This is notoriously difficult when:
- Non-Convexity: The loss function is "bumpy" and lacks the nice mathematical properties that make optimization easy.
- Non-Parametric Policies: We aren't just choosing from a few options; we are competing against a massive class of functions, such as all Lipschitz or Hölder-smooth policies.
Under standard "one-point" bandit feedback, the best possible regret (the difference between our performance and the optimal policy) is often quite slow, typically scaling as $T^{2/3}$ or worse. This paper asks: If we can observe the difference in loss between two actions at each step, can we do better? This "two-point" setup is realistic in scenarios like A/B testing or navigation apps suggesting two alternative routes to different drivers under the same traffic conditions.
Methods
The authors propose a framework based on Hierarchical Discretization and Follow-the-Regularized-Leader (FTRL).
- Policy Trees: Instead of looking at all possible policies at once, they build a tree. The top levels represent coarse approximations of the policy space, while deeper levels provide finer detail.
- Two-Point Estimator: At each round, the learner picks a node in the tree and samples two actions. By observing the difference in their losses, the learner can build a "loss estimator" with much lower variance than standard bandit estimators. Because the losses are Lipschitz (meaning they don't change abruptly), nearby actions have similar losses, which the two-point feedback exploits.
- Nested Regularization: They use a specific "nested negative entropy" regularizer. This allows the algorithm to share information across different branches of the policy tree, preventing the regret from exploding as the tree gets deeper.
- Factorized Implementation (Algorithm 2): For the specific case of Lipschitz policies, the authors designed a computationally efficient version. While general non-parametric methods are often mathematically elegant but computationally impossible, this version runs in $O(\ln T)$ time per round.
Datasets
This is a theoretical paper focused on proving mathematical guarantees (regret bounds). As such, it does not use empirical datasets or benchmarks. The "performance" is measured through rigorous mathematical proofs of upper bounds on regret.
Key Insights and Ideas
- Closing the Gap: The most striking insight is that two-point feedback allows the learner to recover the full-information regret rate ($\sqrt{T}$) in several regimes, such as when the policy class is sufficiently smooth or the dimensions are low.
- Variance Reduction: In standard bandits, you estimate the loss of an action by dividing the observed loss by the probability of picking it. If that probability is small, the estimate is wild (high variance). Two-point feedback allows for a "gradient-like" estimate that is much more stable.
- Structure Matters: The paper shows that the regret doesn't just depend on the number of policies, but on the number of possible action pairs at different levels of the tree. This refined dependence is what allows for the improved rates.
Key Results
The authors prove that their algorithm achieves the following regret rates (simplified):
- $\sqrt{T}$ when the sum of the action dimension ($d$) and the policy complexity ($p$) is less than 2 ($d + p < 2$).
- $T^{1 - 1/(d+p)}$ in higher-dimensional or less smooth cases.
Compared to the best-known rates for one-point bandit feedback ($T^{1 - 1/(d+p+2)}$), this is a substantial improvement. For example, in a simple 1D case with no context, the two-point model hits $\sqrt{T}$, whereas the one-point model is stuck at $T^{2/3}$.
Limitations and Future Work
- The "Two-Point" Cost: The model assumes that playing two actions and incurring their average loss is acceptable. In some high-stakes scenarios (like medical trials), playing a second, potentially worse action just for information might be ethically or financially difficult.
- Computational Generality: While the authors provide an efficient algorithm for Lipschitz policies, the general version for other policy classes (like Hölder-smooth) remains computationally expensive.
- Adversarial Contexts: The current work assumes an "oblivious" environment where contexts don't react to the learner's past actions. Extending this to fully adaptive adversaries remains a challenge.
Summary updated