Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Cost-Aware Near-Optimal Policy Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes cost-aware pure-exploration algorithms (S-P cost for static linear contextual bandits, IG cost for adaptive Bayesian contextual bandits) that reduce the total experimental cost needed to learn a near-optimal contextual policy, evaluated in simulations on voting and court-appearance data.
Problem
Learning a near-optimal contextual bandit policy with pure exploration while accounting for heterogeneous, action-dependent resource costs, rather than only the number of samples.
Approach
Modifies sampler-planner (S-P) and information-directed sampling to choose actions by uncertainty or information gain per unit cost (ratio objectives), instead of ignoring costs, and provides finite-sample simple-regret guarantees when the cost ratio is bounded.
Key results
- On the voting simulation, S-P cost reaches an epsilon-optimal policy at lower cumulative exploration cost than S-P, HATCH, and Random across 50 trials.
- On the court appearance simulation, IG cost requires substantially fewer exploration resources than Random, Thompson, CGP-UCB, and IG to reach a given performance gap.
- The paper proves that the cost-aware algorithms can provably recover epsilon-optimal policies when the ratio between maximum and minimum costs is bounded.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cost-aware uncertainty-per-cost planning (S-P cost) instead of cost-unaware S-P | Static exploration on the voting encouragement simulation · Voting encouragement | cumulative exploration cost to reach a given performance gap | Helped |
| Use cost-aware information gain per unit cost (IG cost) instead of cost-unaware exploration methods | Adaptive exploration on the court appearance simulation · Court appearance | cumulative exploration cost to reach a given performance gap | Helped |
| Use random exploration instead of S-P | Static exploration on the voting encouragement simulation · Voting encouragement | cumulative exploration cost | Helped |
| Use random exploration instead of two sample-efficient alternatives | Adaptive exploration on the court appearance simulation · Court appearance | cumulative exploration cost | Helped |
Surprising findings
- Random sampling outperforms the sample-efficient S-P and several other alternatives in terms of total cost, showing that sample efficiency does not imply cost efficiency.
Limitations
- Algorithms are myopic and not guaranteed to find minimal cumulative cost.
- Experiments are simulations using known, deterministic costs and rejection-sampled or semi-synthetic data.
- Requires a known feature map / realizable linear or parametric reward model.
Experimental setup
Datasets: Gerber, Green, and Larimer 2008 voting encouragement dataset Chohlas-Wood et al. 2021 court appearance simulator
Benchmarks: voting encouragement simulation (Gerber et al. 2008) court appearance simulation (Chohlas-Wood et al. 2021)
Metrics: cumulative exploration cost (USD) performance gap to optimal policy simple regret
Baselines: Random S-P HATCH Thompson sampling CGP-UCB IG
Builds on: sampler-planner (S-P) information-directed sampling HATCH LinUCB
Closest papers by meaning
- PAC-Bayesian Offline Contextual Bandits With Guarantees (ICML 2023 · similarity 0.89)
- Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization (NeurIPS 2023 · similarity 0.89)
- Causal Contextual Bandits with Targeted Interventions (ICLR 2022 · similarity 0.89)
- Optimal Regret for Policy Optimization in Contextual Bandits (ICML 2026 · similarity 0.89)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.88)
- Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.