Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Randomized Confidence Bounds for Stochastic Partial Monitoring
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.
Randomizes the confidence bounds of CBP-based successive-elimination partial monitoring strategies (RandCBP) and proposes CBP* / RandCBP* for contextual partial monitoring, with regret guarantees and a classifier-error-monitoring use case.
Problem
Stochastic partial monitoring: deterministic CBP-based strategies have regret guarantees on easy and hard games but are empirically outperformed by stochastic strategies; existing contextual PM strategies (CBP-side) do not apply to hard games and IDS-based methods scale poorly.
Approach
Replace the deterministic confidence width in CBP's successive elimination criterion with a width scaled by a random variable drawn from a truncated, discretized Gaussian over [A,B] (randomized confidence bounds), preserving regret guarantees since randomized bounds are upper bounded by deterministic ones; extend the contextual CBP-side with pseudo-count exploration (CBP*) to hard games and random
Key results
- RandCBP achieves significantly lower regret (p<0.01) than all baselines in three of four imbalanced/balanced AT and LE settings over T=20k with 96 runs.
- RandCBP* significantly improves over CBP*, STAP, and CESA on contextual AT and LE games (p<0.01).
- In the classifier-monitoring use case, RandCBP-based approach reduces verification cost by 73% relative to explore-commit at tau=0.2 in case 1, with comparable f1-score.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| randomize the confidence bounds in CBP | CBP · Apple Tasting and Label Efficient games, balanced and imbalanced instances | cumulative regret | Helped |
| randomize the confidence bounds in CBP | CBP · Balanced Apple Tasting | cumulative regret: p-value=0.055 | No clear effect |
| randomize the confidence bounds in CBP | CBP · Apple Tasting and Label Efficient contextual games | cumulative regret: p-value<0.01 | Helped |
| use randomized CBP instead of explore-commit | classifier error-rate monitoring, case 1, τ = 0.025 · τ-detection game | number of verifications: 15% | Helped |
| use randomized CBP instead of explore-commit | classifier error-rate monitoring, case 1, τ = 0.2 · τ-detection game | number of verifications: 73% | Helped |
| use randomized CBP instead of explore-commit | classifier error-rate monitoring, case 2, τ = 0.025 · τ-detection game | number of verifications: 18% | Helped |
| use randomized CBP instead of explore-commit | classifier error-rate monitoring, case 2, τ = 0.2 · τ-detection game | number of verifications: 62% | Helped |
| use randomized CBP, CCBP, or explore-commit | classifier error-rate monitoring · τ-detection game, case 1, τ = 0.025 | average F1-score: 0.96±0.15; 0.95±0.16 | No clear effect |
| use randomized CBP, CCBP, or explore-commit | classifier error-rate monitoring · τ-detection game, case 1, τ = 0.2 | average F1-score: 1.0 | No clear effect |
Surprising findings
- In balanced AT, RandCBP is not statistically different from CBP (p=0.055) and TSPM (p=0.854).
Limitations
- Regret bounds are not tight; authors note future work needed for tighter bounds.
- Contextual guarantees for RandCBP* are only proven in the linear setting.
- Game-specific baselines (PGIDS, PGTS, STAP, CESA) are only applicable to specific games.
Experimental setup
Benchmarks: Apple Tasting Label Efficient tau-detection game
Metrics: cumulative regret win-count f1-score number of verifications
Baselines: CBP PM-DMED BPM-Least TSPM TSPM-Gaussian CBP-side IDS-FW PGIDS PGTS STAP CESA Explore-commit
Builds on: CBP CBP-side randomized UCB (Kuang et al.) Thompson sampling
Closest papers by meaning
- Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring (NeurIPS 2025 · similarity 0.89)
- Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring (NeurIPS 2020 · similarity 0.87)
- The Knowledge Gradient for Sequential Decision Making with Stochastic Binary Feedbacks (ICML 2016 · similarity 0.86)
- Phased Exploration with Greedy Exploitation in Stochastic Combinatorial Partial Monitoring Games (NeurIPS 2016 · similarity 0.86)
- Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight (ICLR 2024 · similarity 0.85)
- Online Set Learning from Precision and Recall Feedback (NeurIPS 2026 · similarity 0.85)
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.