Near-Optimal Learning in Parametric Bandits with Action-Dependent Coarsened Feedback

We study a structured stochastic multi-armed bandit problem in which each decision simultaneously determines the learner's reward and the feedback available for learning. At each round, the learner selects a task and an option. Each task is associated with an unknown parameter that governs its reward, while each option has a known reward function of this parameter and determines how information about that reward is observed. Some options may provide fine-grained feedback at the cost of lower immediate reward, whereas others may yield higher reward but return only coarse feedback. This creates an intrinsic trade-off between reward maximization and information acquisition. We formalize this setting as parametric bandits with action-dependent coarsened feedback. For stationary tasks, we propose ACF-UCB, an optimistic algorithm that constructs task-level confidence sets by aggregating information from all atoms of the option-dependent feedback distributions. For piecewise-stationary tasks, we develop SW-ACF-UCB, a sliding-window variant that adapts to temporal changes. We prove high-probability regret bounds for stationary environments and dynamic regret guarantees for piecewise-stationary environments. We also establish lower bounds showing that the dependence on the number of tasks and the horizon is unavoidable, while methods that ignore the shared parametric structure suffer substantially larger regret.