AT-UCB uses a cheap abstracted causal model to filter out suboptimal actions before running UCB on the expensive base model, with a regret bound that improves when the abstraction is accurate.
Bandits with Mean Bounds
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We study a variant of the bandit problem where side information in the form of bounds on the mean of each arm is provided. We prove that these translate to tighter estimates of subgaussian factors and develop novel algorithms that exploit these estimates. In the linear setting, we present the Restricted-set OFUL (R-OFUL) algorithm that additionally uses the geometric properties of the problem to (potentially) restrict the set of arms being played and reduce exploration rates for suboptimal arms. In the stochastic case, we propose the non-optimistic Global Under-Explore (GLUE) algorithm which employs the inferred subgaussian estimates to adapt the rate of exploration for the arms. We analyze the regret of R-OFUL and GLUE, showing that our regret upper bounds are never worse than that of the standard OFUL and UCB algorithms respectively. Further, we also consider a practically motivated setting of learning from confounded logs where mean bounds appear naturally.
fields
cs.LG 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Using causal abstractions to accelerate decision-making in complex bandit problems
AT-UCB uses a cheap abstracted causal model to filter out suboptimal actions before running UCB on the expensive base model, with a regret bound that improves when the abstraction is accurate.