- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper proposes Causal Tsallis-INF for causal bandits with mediator feedback. It provides regret guarantees for both stochastic and adversarial environments and shows improved performance over several existing methods.
Critical strengths
The paper provides meaningful theoretical contributions, including regret bounds that adapt to both action and mediator complexity. The best-of-both-worlds guarantees improve upon prior work and are supported by experiments.
Critical weaknesses
The nonstationary experiments keep the optimal action and suboptimality gaps fixed. These settings do not fully test adaptation when the best action changes over time.
The proposed algorithm requires numerical optimization at each round. Its computational cost and scalability are not sufficiently evaluated, especially compared with simpler bandit algorithms.
Questions for authors
Can the authors evaluate settings where the optimal action changes over time, while clearly distinguishing this from the static-regret guarantee?
How does the per-round computation time scale with the number of actions and mediators?
In which settings does using mediator feedback provide a clear advantage over standard Tsallis-INF?
2 comments
Thank you for the detailed responses. The clarification on static regret is helpful, and I agree that changing the optimal action is not required for the theoretical guarantees. The computational cost analysis is useful, although the 5–13x runtime overhead remains a practical limitation. The examples illustrating the benefit of mediator feedback also address my third question. Overall, my concerns have been reasonably addressed, and I will maintain my rating.
Q1:
Theorem 4.1 provides regret guarantee against the best fixed action in hindsight at time T. The optimal action is allowed to change over time, for example, it can be a1 at time T0<T and a2 at time T, but the regret at time T is computed against the cumulative loss of a fixed action that is optimal at time T. Our algorithm does not aim to minimize the regret against a switching baseline, and the same holds for all the algorithms we compare ourselves to. However, we emphasize that the adversarial regret guarantee holds regardless of whether the optimal action has been the same all the way through or changed over time.
We further note that in comparisons against a fixed baseline (as we study), changing the optimal action along the way can be used to “help” underperforming algorithms. For example, if some algorithm overplays a suboptimal action in time interval up to T0, turning that action into optimal after T0 will help the algorithm at evaluations beyond T0. Therefore, such experiments will lack clear interpretation.
Q2:
For regularization in the mediator space we have to calculate an approximate solution to FTRL optimization procedure (in contrast to analytical solution of standard Tsallis-INF).
For dense M (worst case), the per-round cost is
N_t\bigl(|\mathcal Z||\mathcal A|^2+|\mathcal A|^3\bigr) +(E_t+1)|\mathcal Z||\mathcal A| \right),$$ where $N_t$ counts Newton steps and $E_t$ counts additional evaluations, including line searches. There were on average $3.30$ and $3.17$ per round of these in the main paper experiment, respectively. Memory requirement is $O(|\mathcal Z||\mathcal A|+|\mathcal A|^2)$. Iteration counts depend on numerical tolerance and conditioning. Experiments we have run have been completed within hour. Classical Tsallis-INF requires only one computation costing $O(N_t|\mathcal A|)$ per iteration. Fixed-mechanism EXP4MF can run in $O(|Z||\mathcal A|)$ per round using only the observed mediator's row, assuming its capacity-based tuning is supplied. Practically, in our experiment with 80 actions and 30 mediators Causal Tsallis-INF took 5–13 times longer to run than EXP4MF. **Q3:** Settings, where mediator feedback provides a clear advantage over standard Tsallis-INF are illustrated in Figures 1(b) and 1(c). In both examples the regret of Tsallis-INF grows with the gap in the action space, but the regret of Causal Tsallis-INF stays unaffected, and in the case of Figure 1(c) even constant. And both examples can be scaled up to larger $|\mathcal A|$ with the same $|\mathcal Z|=2$, further increasing the regret of Tsallis-INF, without affecting the regret of Causal Tsallis-INF. In general, mediator feedback is useful for two reasons: information sharing across actions and an extra tool to eliminate suboptimal alternatives. The advantage of information sharing is most prominent when mediator feedback provides full information (as in Figure 1(c)), leading to constant regret in the stochastic case. Our experimental scenarios in the main text and appendix provide further examples and evidence for when using mediator feedback provide a clear advantage over standard Tsallis-INF.