RECORD
Conservative Exploration using Interleaving
Machine Learning · Submitted 3 Jun 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Our real-world experiments show that our algorithms can learn to recommend K most attractive movies without ever violating a strict production constraint, both overall and subject to a diversity constraint.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
In many practical problems, a learning agent may want to learn the best action in hindsight without ever taking a bad action, which is significantly worse than the default production action. In general, this is impossible because the agent has to explore unknown actions, some of which can be bad, to learn better actions. However, when the actions are combinatorial, this may be possible if the unknown action can be evaluated by interleaving it with the production action. We formalize this concept as learning in stochastic combinatorial semi-bandits with exchangeable actions. We design efficient learning algorithms for this problem, bound their n-step regret, and evaluate them on both synthetic and real-world problems. Our real-world experiments show that our algorithms can learn to recommend K most attractive movies without ever violating a strict production constraint, both overall and subject to a diversity constraint.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In many practical problems, a learning agent may want to learn the best action in hindsight without ever taking a bad action, which is significantly worse than the default production action. | background 1.00 | 0.07 | 0.05 | hedged possibility 0.95 |
| s1 | In general, this is impossible because the agent has to explore unknown actions, some of which can be bad, to learn better actions. | background 0.93 | 0.08 | 0.03 | asserted 0.98 |
| s2 | However, when the actions are combinatorial, this may be possible if the unknown action can be evaluated by interleaving it with the production action. | background 0.66 | 0.11 | 0.28 | hedged possibility 0.99 |
| s3 | We formalize this concept as learning in stochastic combinatorial semi-bandits with exchangeable actions. | contribution 0.61 | 0.77 | 0.07 | asserted 0.98 |
| s4 | We design efficient learning algorithms for this problem, bound their n-step regret, and evaluate them on both synthetic and real-world problems. | contribution 0.96 | 0.97 | 0.10 | asserted 0.99 |
| s5 | Our real-world experiments show that our algorithms can learn to recommend K most attractive movies without ever violating a strict production constraint, both overall and subject to a diversity constraint. | result 1.00 | 0.97 | 0.70 | asserted 0.97 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
In many practical problems, a learning agent may want to learn the best action in hindsight without ever taking a bad action, which is significantly worse than the default production action. In general, this is impossible because the agent has to explore unknown actions, some of which can be bad, to learn better actions. However, when the actions are combinatorial, this may be possible if the unknown action can be evaluated by interleaving it with the production action. We formalize this concept as learning in stochastic combinatorial semi-bandits with exchangeable actions. We design efficient learning algorithms for this problem, bound their n-step regret, and evaluate them on both synthetic and real-world problems. Our real-world experiments show that our algorithms can learn to recommend K most attractive movies without ever violating a strict production constraint, both overall and subject to a diversity constraint.
Human review
How the literature uses it
2 arXiv papers cite this in 2 sentences
Papers citing it · 1 sentence without a confident label
Cites it as background 1 paper
-
Another variant of safety w.r.t a baseline policy has also been studied in [ref] in the multi-armed bandits framework.
Stage-wise Conservative Linear Bandits · Previous work · 0.96
What it cites · 5 sentences without a confident label
Uses the method or tool of 1 paper
-
The same approach was used in Optimistic Matroid Maximization (OMM) of [ref] .
Matroid Bandits: Fast Combinatorial Optimization with Learning · Algorithm · 0.90
Compares with 1 paper
-
In <ref>, we solve two recommendation problems using $$, and validate that its regret is no higher than $K-1$ times that of a non-conservative matroid bandit algorithm $$ [ref] . $$ violates our conservative constraint multiple times.
Matroid Bandits: Fast Combinatorial Optimization with Learning · Experiments · 0.97
Cites as background 2 papers
-
Online learning with matroids was introduced by [ref] , and also studied by [ref] .
Matroid Bandits: Fast Combinatorial Optimization with Learning · Related Work · 1.00
-
[ref] study contextual bandits and propose diversity assumptions on the environment.
Mostly Exploration-Free Algorithms for Contextual Bandits · Related Work · 0.98
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.