Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Factored-Reward Bandits with Intermediate Observations

ICML 2024 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Causal and structured bandits

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.

Introduces Factored-Reward Bandits, where each action component yields a noisy intermediate observation and the reward is their product; derives regret lower bounds and proposes F-UCB (worst-case optimal up to logs) and F-Track (asymptotically instance-optimal).

Problem

Sequential decision problems where the learner picks an action vector whose components each produce an observable intermediate effect, and the reward is the product of these effects; standard bandits ignore this structure, leading to large action spaces and amplified noise.

Approach

Exploits the factored structure by treating each action component's intermediate observation as a separate sample (information sharing across action vectors), using per-component UCB indices (F-UCB) and a bound-tracking planner over component pull proportions (F-Track) to match the instance-dependent lower bound.

Key results

• F-UCB achieves worst-case regret O~(sigma d sqrt(kT)), matching the Omega(sigma d sqrt(kT)) lower bound up to logarithmic factors.
• F-UCB's instance-dependent regret does not match the lower bound: its ratio to the lower bound grows roughly linearly in d for large gaps (Remark 4.1, Figure 2).
• F-Track matches the instance-dependent asymptotic lower bound (limsup regret / log T = C(nu)).

Measured effects reported in the paper

Surprising findings

• Without intermediate observations, the exponential dependence on sigma d is unavoidable even with the factored structure (Theorem 3.2).
• The product reward of subgaussian components is not subgaussian for d>=3 and has no MGF, so standard UCB1 does not apply directly.

Limitations

• F-Track is only asymptotically optimal; no non-asymptotic instance-dependent optimality is shown.
• Analysis assumes the product aggregation function and independent intermediate observations with a known common subgaussian proxy.
• Experiments are limited to simulated instances in the appendix.

Experimental setup

Benchmarks: simulated FRB instances (Figure 2, Appendix E)

Metrics: expected cumulative regret regret ratio to instance-dependent lower bound

Baselines: Robust-UCB (median of means) Factored Bandit TEA instance-dependent lower bound

Builds on: UCB1 Robust-UCB (median of means) Factored Bandit TEA Lattimore-Szepesvari tracking of the bound

Closest papers by meaning

• Factored Bandits (NeurIPS 2018 · similarity 0.91)
• Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.90)
• Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.90)
• Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.90)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.89)
• Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.89)