Exploration scavenging
The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
We examine the problem of evaluating a policy in the contextual bandit setting using only observations collected during the execution of another policy. We show that policy evaluation can be impossible if the exploration policy chooses actions based on the side information provided at each time step. We then propose and prove the correctness of a principled method for policy evaluation which works when this is not the case, even when the exploration policy is deterministic, as long as each action is explored sufficiently often. We apply this general technique to the problem of offline evaluation of internet advertising policies. Although our theoretical results hold only when the exploration policy chooses ads independent of side information, an assumption that is typically violated by commercial systems, we show how clever uses of the theory provide non-trivial and realistic applications. We also provide an empirical demonstration of the effectiveness of our techniques on real ad placement data.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Finite-time Analysis of the Multiarmed Bandit Problem
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002) · Machine Learning · doi:10.1023/a:1013689704352 · Cited by 6,033 · cited 2×
“Introduction The k-armed bandit problem (Lai & Robbins, 1985; Berry & Fristedt, 1985; Auer et al., 2002; Even-Dar et al., 2006) has been studied in great detail, primarily because it can be viewed as a minimal formalization of the exploration problem faced by any autonomous agent.”
BackgroundCumulated gain-based evaluation of IR techniques
Järvelin, K., & Kekäläinen, J. (2002) · ACM Transactions on Information Systems · doi:10.1145/582415.582418 · Cited by 4,841 · cited 1×
“A common technique for estimating ADCs borrowed from the information retrieval literature is discounted cumulative gain (J¨arvelin & Kek¨al¨ainen, 2002).”
Method
Cited by
Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
Levine, S., Kumar, A., Tucker, G., & Fu, J. (2020) · arXiv · doi:10.48550/arxiv.2005.01643 · Cited by 824
“In contrast to the other applications discussed, policy evaluation for recommender systems is typically formulated within a contextual bandit problem (Langford et al., 2008; Li et al., 2010), where states may correspond to user history and actions correspond to recommendations.”
ResultUnbiased Learning-to-Rank with Biased Feedback
Joachims, T., Swaminathan, A., & Schnabel, T. (2017) · Proceedings of the Tenth ACM International Conference on Web Search and Data Mining · doi:10.1145/3018661.3018699 · Cited by 531
“Unlike the uniform ranking randomization of [28] (with its high performance impact) or swapping adjacent pairs as in [5], we swap documents in different ranks to the top position randomly as in [12].”
BackgroundMethodUnbiased offline evaluation of contextual-bandit-based news article recommendation algorithms
Li, L., Chu, W., Langford, J., & Wang, X. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935878 · Cited by 443
Self-citationDoubly Robust Policy Evaluation and Learning
Dudı́k, M., Langford, J. C., & Li, L. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1103.4601 · Cited by 375
Self-citationOnline Task Assignment in Crowdsourcing Markets
Ho, C.-J., & Vaughan, J. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v26i1.8120 · Cited by 293
Metadata
- Authors
- Langford, J., Strehl, A., & Wortman, J.
- Venue
- Proceedings of the 25th international conference on Machine learning - ICML '08
- Publisher
- ACM Press
- Published
- 2008
- Pages
- 528-535
- OpenAlex
- W2293743194
- Cited by
- 108
- References
- 2
- FWCI
- 9.70
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Exploration scavenging. https://app.cochat.ai/papers/10.1145/1390156.1390223
- The paper
- Langford, J., Strehl, A., & Wortman, J. (2008). Exploration scavenging. Proceedings of the 25th international conference on Machine learning - ICML '08. https://doi.org/10.1145/1390156.1390223
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.