PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Search Better Than Your Teacher

Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé, John Langford

arXiv:1502.02206v2cs.LGstat.ML

TL;DR

Prior learning-to-search methods mainly imitate a reference policy, leaving open whether learning can improve on a poor reference. The paper introduces LOLS, which combines reference-policy and learned-policy deviation regret, achieves local optimality, and extends the approach to structured contextual bandits.

  • Problem

    Existing L2S guarantees compare the learned policy with a reference policy assumed to perform well, providing no useful guarantee when that reference is suboptimal.

  • Method

    LOLS learns online using learned-policy roll-in, reference-or-learned rollouts, and cost-sensitive updates, then adapts the procedure to structured contextual bandits with exploration.

  • Results

    LOLS guarantees low regret relative to the reference policy and one-step deviations from the learned policy, and can significantly outperform the reference policy on real-world datasets.

  • Takeaways & Limitations

    The local-optimality guarantee allows learning to search to improve on a poor reference and supports structured prediction with partial feedback.

  • Takeaways & Limitations

    Guaranteeing one-step-deviation regret against an arbitrarily bad reference can take exponentially long, and tractability depends on structural assumptions.

Abstract

from arXiv · show

Methods for learning to search for structured prediction typically imitate a reference policy, with existing theoretical guarantees demonstrating low regret compared to that reference. This is unsatisfactory in many applications where the reference policy is suboptimal and the goal of learning is to improve upon it. Can learning to search work even when the reference is poor? We provide a new learning to search algorithm, LOLS, which does well relative to the reference policy, but additionally guarantees low regret compared to deviations from the learned policy: a local-optimality guarantee. Consequently, LOLS can improve upon the reference policy, unlike previous algorithms. This enables us to develop structured contextual bandits, a partial information structured prediction setting with many potential applications.

1. Introduction

Learning to search converts structured prediction into sequential decision-making, but prior methods mainly guarantee performance relative to a reference policy. LOLS addresses poor references by combining reference regret with local-optimality guarantees and extends the framework to structured contextual bandits.

  • Motivation: Structured prediction requires joint decisions over interdependent outputs and observes a joint loss.Learning to search represents this problem as a search space with actions, state features, a reference policy, and a learned policy.
  • Limitations of prior work: Existing L2S theory guarantees that a well-trained learner is nearly as good as the reference policy, assuming that policy performs well.This leaves existing approaches unable to provide guarantees when the reference is suboptimal.
  • Applications: Poor-reference settings arise when computational constraints make the reference policy suboptimal, especially in structured contextual bandits with feedback-based quality signals.A high-profile website’s page layout is given as an example involving many interdependent display decisions.
  • LOLS: LOLS combines regret to the reference policy with regret to one-step deviations from the learned policy.The second component yields an approximate local-optimality guarantee even when the reference policy is very suboptimal.
  • Contributions: LOLS can outperform poor reference policies in practice and is extended to structured contextual bandits.The paper reports empirical improvement over the reference policy on real-world datasets and develops a corresponding bandit modification.

2. Learning to Search

Learning to search defines structured prediction as policy-guided traversal through a feature-based search space. LOLS learns cost-sensitive action choices by rolling in with a learned policy and evaluating actions with a reference-or-learned rollout mixture.

  • Search formulation: A structured prediction input induces a search space with an initial state, deterministic transitions, end-state losses, and state features.Features encode the input and previous predictions, while policies choose actions using feature vectors.
  • Search formulation: Policies traverse the search space by selecting actions that determine successive states until an end state is reached.Each end state corresponds to a structured output and has an associated loss.
  • Learning assumptions: The framework assumes access to a no-regret online cost-sensitive classification algorithm.Examples include online perceptron or online ridge regression combined with SECOC.
  • LOLS procedure: LOLS constructs T cost-sensitive multiclass examples by evaluating available actions at each decision point.The cost of an action is its loss difference relative to the best action after completing the trajectory with a rollout policy.
  • LOLS procedure: LOLS rolls in with the current learned policy and rolls out with a mixture that follows the reference policy with probability β or the learned policy otherwise.The resulting examples are supplied to an online cost-sensitive learner to update the policy.

Mixture Learned

The paper contrasts roll-in and roll-out strategies, highlighting failures caused by relying on the reference policy and favoring strategies that preserve local-improvement information.

  • Strategy comparison: Strategies using unsuitable roll-in or roll-out policies can produce large structured regret or policies worse than one-step deviations.The table labels these outcomes as “Inconsistent” and “Not locally opt.”
  • Strategy comparison: The “RL” strategy reduces structure learning to reinforcement learning, which the paper characterizes as much harder.The table marks this strategy separately from the favored “Good” strategy.

3. Theoretical Analysis

The theoretical analysis shows that LOLS must combine roll-in and roll-out choices carefully to learn from mistakes and obtain guarantees relative to both the reference policy and one-step deviations. These guarantees hold even for arbitrarily suboptimal references, but local improvement can be exponentially hard without structural assumptions.

  • 3.1. The Bad Choices: Rolling in with the reference policy can hide states reached after earlier mistakes, yielding low cost-sensitive regret despite poor test-time structured performance.In the example, state s3 is never observed during training, while the learned policy can perform as badly as possible there.
  • 3.1. The Bad Choices: LOLS rolls in with the learned policy and mixes rollout policies, producing cost-sensitive examples that expose states and actions needed for local improvement.The analysis reports that learned-policy roll-in is robust to the failure modes illustrated by the bad-choice examples.
  • 3.1. The Bad Choices: Rolling out with the reference policy can make the learner blind to beneficial one-step deviations when that reference is suboptimal or outside the hypothesis class.The resulting policy may have low classification regret even though a one-step deviation substantially improves structured performance.
  • 3.2. Regret Guarantees: LOLS minimizes a convex combination of regret to the reference policy and regret to its own one-step deviations, with the averaged policy satisfying the resulting theorem bound.The guarantee is parameterized by the mixing parameter β and the quantity δN.
  • 3.2. Regret Guarantees: The theorem does not assume reference-policy quality, so LOLS can either remain competitive with the reference and nearly locally optimal or improve substantially upon it.When the reference is optimal, the analysis gives competition with one-step deviations; when it is very suboptimal, the reference-regret term can be negative.
  • 3.2. Regret Guarantees: As N →∞ with a no-regret cost-sensitive classifier, δN →δclass, but an asymptotic gap can remain for β ∈(0, 1) even with an unrestricted policy class.Avoiding this gap would require controlling reference regret and one-step-deviation regret individually.
  • 3.3. Hardness of local optimality: Reaching a one-step-deviation local optimum can take exponentially long from an arbitrary starting policy, even for an algorithm with access to exact policy costs.The lower bound shows that this difficulty persists for a more powerful algorithm than existing learning-to-search methods.

4. Structured Contextual Bandit

The paper extends LOLS to structured contextual bandits, where only the loss of one structured prediction is observed. Its ϵ-greedy procedure alternates exploitation with randomized LOLS updates and evaluates regret against mixtures of reference policies and one-step deviations.

  • Structured contextual bandits reveal only the loss of a single structured label, with applications including webpage layout and personalized search.
  • The bandit setting assumes losses in [0, 1], search depth T, at most K actions per state, a policy class Π, and a reference policy without access to the true label.
  • The algorithm uses ϵ-greedy exploration: it exploits the learned policy with probability 1 −ϵ and otherwise performs a randomized LOLS update.
  • Regret is measured against a comparator combining the reference policy with the best one-step deviation from the averaged learned policy.
  • Theorem 5 provides a regret bound for Algorithm 2, and the subsequent corollary gives a high-probability guarantee under a no-regret learner.
  • During exploration, the procedure samples a time and action, rolls in with the learned policy, and rolls out with the reference policy with probability β or the learned policy otherwise.

5. Experiments

Experiments across cost-sensitive classification, POS tagging, and dependency parsing support the theoretical analysis. Reference roll-in performs poorly, while mixture roll-outs help when the reference policy is suboptimal, and LOLS significantly outperforms SEARN on all tasks.

  • Experiments cover cost-sensitive multiclass classification, part-of-speech tagging, and dependency parsing.
  • Cost-Sensitive Multiclass classification: Cost-sensitive classification uses a binary search tree over labels, with trajectory loss defined by the cost of the terminal label.
  • Part of speech tagging: POS tagging uses left-to-right prediction on 38k training and 11k test sentences from the Penn Treebank.
  • The reported table metrics are average cost for classification, accuracy for POS tagging, and UAS for dependency parsing.
  • The comparison varies learned or reference roll-in with learned, mixture, or reference roll-out, and includes SEARN as a baseline.
  • Across the three tasks, reference roll-in is always bad; reference roll-outs help with optimal references, whereas mixture roll-outs perform substantially better with suboptimal or bad references.

6. Proofs of Main Results

The proofs establish regret guarantees through policy-comparison identities, exploration–exploitation analysis, and a hypercube-path lower bound. They show that local one-step-deviation updates can require exponentially many moves in the worst case.

  • Policy comparison: Lemma 1 expresses the loss difference between two policies as an expected difference in downstream action values.The identity is proved by defining policies that switch from one policy to the other after each time step and summing the resulting differences.
  • Regret analysis: The regret analysis decomposes rounds into exploration and exploitation, bounding exploration regret directly and controlling exploitation through exploration updates.The exploitation-round regret is bounded by δ_{n_i}, where n_i is the number of exploration rounds before round i.
  • Regret analysis: Choosing ϵ = (KT)2/3(log(N|Π|)/N)1/3 completes the stated regret proof.This parameter choice is made after substituting the preceding bounds into the regret expression.
  • Regret analysis: A Chernoff bound controls the number of exploration rounds around its expectation, enabling a high-probability regret bound after an initial allowance for early rounds.The proof uses n_i ≤ ϵi/2 after a threshold and allows regret 1 on the first i_0 rounds.
  • Lower bound: The lower-bound construction represents policies as vertices of a T-dimensional hypercube and forces updates along a long path of one-step deviations.The longest relevant path is a snake-in-the-box path with length Θ(2^T), and suitable costs force traversal time Θ(2^T).
  • Lower bound: The lower-bound cost structure can force Algorithm 1 to follow only one-step deviations despite its mini-batch cost-sensitive updates.Assigning maximal costs to selected policies induces correspondingly large action costs in the cost-sensitive problem.

A. Details of cost-sensitive reduction

The experimental reduction uses cost-sensitive multiclass prediction to estimate action costs and select the lowest-cost label. The representation supports either class-specific predictors or an equivalent common predictor over expanded features.

  • Cost-sensitive reduction: CSOAA trains regressors to predict class-specific costs and selects the class with the smallest predicted cost.The method takes feature vectors x_{t,i} for each class and predicts the corresponding costs c_{t,i}.
  • Cost-sensitive reduction: A common feature vector can be converted into class-specific expanded features, making one common predictor representationally equivalent to K separate predictors.For z_t ∈ R^d, the construction places z_t in the ith block of x_{t,i} and zeros elsewhere.
  • Cost-sensitive reduction: The online update depends on the predictor family, with ridge regression and online gradient descent given as alternatives.The experiments use a more sophisticated linear online-gradient-descent variant.

B. Details of Experiments

The experiments implement LOLS and related methods in Vowpal Wabbit using task-specific search configurations. The reported datasets are available upon request.

  • Implementation: The implementation uses Vowpal Wabbit version 7.8 with search options controlling roll-in, roll-out, exploration, interpolation, and training passes.LOLS uses search rollin, search rollout, and search beta; SEARN uses interpolation policy and multiple passes.
  • Task configurations: The evaluation configures separate search tasks for POS tagging, dependency parsing, and cost-sensitive multiclass prediction.Each task uses its own search horizon and feature or label settings.
  • Data availability: The datasets used in the experiments are available upon request.
Loading 1502.02206v2…