acceptodds
Under review as a conference paper at ICLR 2027

BEST-OF-BOTH-WORLDS CAUSAL BANDITS WITH MEDIATOR FEEDBACK

Abstract

We study a bandit setting described by a causal graph , where is an action, is an observable mediating state separating from the loss , and is an unobserved variable. The setting has been proposed and studied independently in the causality literature under the name of *causal bandits with post-action context*, and in the classical bandit literature under the name of *bandits with mediator feedback*. Similar to both bodies of literature, we assume that the mapping is fixed. We propose a best-of-both-worlds algorithm, *Causal Tsallis-INF*, which provides a worst-case regret guarantee in case of adversarial and instance-dependent regret guarantees for stochastic , as well as other forms of for which the regret satisfies the self-bounding constraint of Zimmert, Seldin (2021). Our setting matches the one studied by Eldowa et al. (2024) in the classical bandit literature and generalizes the setting studied in the causal bandit literature, where is assumed to be stochastic. We advance both strands of literature. Our stochastic regret guarantee improves the logarithmic dependence on the horizon in the EXP4 analysis of Eldowa et al. (2024) and adapts to both action and attainable mediator complexity. Our adversarial guarantee also extends beyond the stochastic assumptions underlying the causal bandit methods. We further provide an empirical evaluation demonstrating that for stochastic our algorithm performs comparably to state-of-the-art Causal Thompson Sampling and Causal UCB2 algorithms, and that, in contrast to our algorithm, the latter are not robust to non-stochastic , at the same time, our algorithm consistently outperforms the EXP4 algorithm in all the experiments. References: Eldowa et al. (2024): Information capacity regret bounds for bandits with mediator feedback. JMLR Zimmert, Seldin (2021): Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits , JMLR

Primary area:
reinforcement learning
Keywords:
Causal Bandits, Mediator Feedback, Best-of-Both-Worlds Bandits, Post-Action Context

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_C9ShOpenReview ↗
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

Q1:

Theorem 4.1 provides regret guarantee against the best fixed action in hindsight at time TT. The optimal action is allowed to change over time, for example, it can be a1a_1 at time T0<TT_0<T and a2a_2 at time TT, but the regret at time TT is computed against the cumulative loss of a fixed action that is optimal at time TT. 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 T0T_0, turning that action into optimal after T0T_0 will help the algorithm at evaluations beyond T0T_0. 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 MM (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.

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.

Reviewer_1YALOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies a bandit problem on the causal graph A→Z→ℓ←UA \to Z \to \ell \leftarrow U with a known M:A→ZM: A \to Z, where the learner observes the mediator ZtZ_t and the loss ℓt(Zt)\ell_t(Z_t). This setting is a mixture of “causal bandits with post-action context” and “bandits with mediator feedback,” and proposes Causal Tsallis-INF which is an FTRL algorithm with a hybrid regularizer. The main results are a best-of-both-worlds guarantee: a worst-case adversarial bound and an instance-dependent bound. Experiments on synthetic environments, random graphs, a misspecification study, and the Project STAR data compare against EXP4MF, Causal UCB/TS, PE, and CUCB2.

Critical strengths
  1. ** Novel Regularizer. ** Simultaneous adversarial O~(min⁡{∣A∣,∣Z∣}T)\tilde{O}(\sqrt{\min\{|\mathcal{A}|,|\mathcal{Z}|\}T}) and stochastic O(min⁡{SA,SZa}log⁡T)O(\min\{S_\mathcal{A},S_\mathcal{Z}^\mathrm{a}\}\log T), enabled by a hybrid regularizer ψ∧=max⁡{ψA,ψJ}\psi_\wedge=\max\{\psi_\mathcal{A},\psi_\mathcal{J}\} with genuinely new per-mediator curvature lemmas.

  2. Shows causal bandits with post-action context ≡\equiv bandits with mediator feedback. Over Eldowa et al. (2024): log⁡T\log T vs. (log⁡T)2(\log T)^2, and adapts to min of action/mediator complexity, not just action.

  3. Experiments to support their claims in practice.

Critical weaknesses
  1. No lower bounds. The claim is just upper-bound and none of the min⁡{∣A∣,∣Z∣}\min\{|\mathcal{A}|,|\mathcal{Z}|\} or min⁡{SA,SZa}\min\{S_\mathcal{A},S_\mathcal{Z}^\mathrm{a}\} is shown to be tight.

  2. Adversarial bound doesn’t dominate prior work. Because C(M)≤min⁡{∣A∣,∣Z∣}−1\mathcal{C}(M)\le\min\{|\mathcal{A}|,|\mathcal{Z}|\}-1, Eldowa’s O~(C(M)T)\tilde{O}(\sqrt{\mathcal{C}(M)T}) can be much smaller than this paper’s O~(min⁡{∣A∣,∣Z∣}T)\tilde{O}(\sqrt{\min\{|\mathcal{A}|,|\mathcal{Z}|\}T}) on low-capacity channels. The two rates are not uniformly ordered, so the claim to “advance both strands” overstates the adversarial contribution.

  3. I believe knowing MM (the distribution of mediator given each action is a strong assumption). I understand that authors note this as a limitation of this work but in real world scenarios you usually don't have access to MM.

Questions for authors
  1. Is it possible to estimate MM from data and adapt the algorithm so that it works without knowing MM exactly? Prior work suggests this direction is feasible. (e.g., [2] estimates the mediator distribution pm,ap_{m,a} without degrading the stochastic regret rate, and [1] shows a nontrivial estimate of the marginals is both necessary and sufficient for better-than-worst-case rates.) Can a plug-in estimate M^\widehat{M} be carried into the best-of-both-worlds analysis, at least on the stochastic side, and how would the estimation error enter the bound?

  2. Can you give a concrete instance with low channel capacity (C(M)≪min⁡{∣A∣,∣Z∣}\mathcal{C}(M)\ll\min\{|\mathcal{A}|,|\mathcal{Z}|\}) where the bound of [3] O~(C(M)T)\tilde{O}(\sqrt{\mathcal{C}(M)T}) is much smaller than your bound, and report how Causal Tsallis-INF empirically compares there?

  3. Is there a lower bound (even a conjecture) showing that min⁡{∣A∣,∣Z∣}\min\{|\mathcal{A}|,|\mathcal{Z}|\} or min⁡{SA,SZa}\min\{S_\mathcal{A},S_\mathcal{Z}^\mathrm{a}\} is unavoidable, i.e., that no algorithm can do better while retaining adversarial robustness?

[1] Liu, Attias, Roy. Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals. ICML 2024. [2] Mahrooghi et al. Multi-armed Bandits with Missing Outcomes. UAI 2025. [3] Eldowa, Cesa-Bianchi, Metelli, Restelli. Information Capacity Regret Bounds for Bandits with Mediator Feedback. JMLR 2024.

2 comments
AuthorsOpenReview ↗

Response to Q1-Q3

Q1:

Yes, it is possible to use an empirical estimate M^\hat M instead of the true MM. We have provided an empirical evaluation in the Appendix 4, paragraph Robustness to nonstationarity, Figure 5. In this evaluation our algorithm retains its performance to a large extent. It is also possible, but non-trivial, to study how the estimation error would enter the bounds. We believe that such study deserves a separate publication and have mentioned this direction in future work.

Q2:

A very simple example is to take M⋅,a=1∣Z∣M_{\cdot,a}=\frac{1}{|\mathcal Z|} (i.e., every action maps uniformly at random to any mediating state). Then C(M)=0\mathcal C(M)=0, whereas min⁡(∣A∣,∣Z∣)\min(|\mathcal A|,|\mathcal Z|) can be arbitrarily large. However, note that in this case the regret of any algorithm is zero.

More generally, for ∣A∣=∣Z∣=N|\mathcal A|=|\mathcal Z|=N, s∈[0,1]s\in[0,1], and Mz,a=1−sN+s 1(z=a)M_{z,a}=\frac{1-s}{N}+s\,\mathbf 1(z=a), Eldowa et al. (2024, Section 3.3.2) show that C(M)=s2(N−1)\mathcal C(M)=s^2(N-1), and so for small ss, C(M)≪min⁡(A∣,∣Z∣)\mathcal C(M)\ll\min(\mathcal A|,|\mathcal Z|). We note that Eldowa et al. obtain the regret bound depending on C(M)\mathcal C(M) solely through the analysis and a slight modification of the learning rate, without modifying the algorithm. Therefore, we expect that the same improvement can be obtained for our algorithm, but since the dependence on C(M)\mathcal C(M) is not the main focus of our work, we have refrained from it to maintain clear exposition of our contributions. We also note that for s<1s<1 the example above exhibits full observability and our separate stochastic guarantee (the last inequality in Theorem 4.1) is O(1)O(1).

By your request, we have made an empirical evaluation of an example with C(M)≪min⁡(∣A∣,∣Z∣)\mathcal C(M)\ll\min(|\mathcal A|,|\mathcal Z|). As we demonstrate below, our algorithm still outperforms EXP4MF. We take Bernoulli mediator means (0.45,0.55,…,0.55)(0.45,0.55,\ldots,0.55) and 0<s<10<s<1, with Δmin⁡=0.1s\Delta_{\min}=0.1s, SA=10(N−1)/sS_A=10(N-1)/s, and SZa=0S_Z^a=0.

We tested N=2N=2, T=100,000T=100{,}000, over 10 paired runs, using our paper's parameters c=0.7c=0.7, ρ=0.015\rho=0.015, α=2/3\alpha=2/3 for Causal Tsallis-INF, and RV cutoff 16/t16/t. The table below gives the mean pseudo-regret.

ssCausal Tsallis-INFEXP4MF (Thm. 3)
1148.1400±15.888748.1400\pm15.88871408.9800±72.60251408.9800\pm72.6025
0.80.87.3280±4.69907.3280\pm4.69901122.8560±65.36321122.8560\pm65.3632
0.50.51.7450±1.12521.7450\pm1.1252700.2900±37.5695700.2900\pm37.5695
0.20.20.3660±0.36170.3660\pm0.3617281.1080±15.8285281.1080\pm15.8285
0.020.020.2128±0.13920.2128\pm0.139228.1472±1.529228.1472\pm1.5292

Mean cumulative pseudo-regret over 10 paired runs with half width of the t-student distribution. The smaller ss becomes the lower the scale of the regret, but also the smaller the gap.

Q3:

Assume min⁡(∣A∣,∣Z∣)≥2\min(|\mathcal A|,|\mathcal Z|)\ge2. If MM is the identity matrix, our problem reduces to a standard multiarmed bandit problem with ∣A∣=∣Z∣|\mathcal A|=|\mathcal Z| actions. Furthermore, in this case SA=SZaS_{\mathcal A}=S_{\mathcal Z}^a. An adversarial lower bound for a standard multiarmed bandit is Ω(∣A∣T)=Ω(∣Z∣T)\Omega(\sqrt{|\mathcal A|T})=\Omega(\sqrt{|\mathcal Z|T}) and an asymptotic stochastic lower bound for uniformly efficient algorithms with Bernoulli losses whose means are close to 12\frac{1}{2} is Ω(SAlog⁡T)=Ω(SZalog⁡T)\Omega(S_{\mathcal A}\log T)=\Omega(S_{\mathcal Z}^a\log T) (Lai and Robbins, 1985). Therefore, all the four terms are part of lower bounds for the corresponding regimes individually and, consequently, for best-of-both-worlds.

The adversarial argument also extends to unequal dimensions. For ∣Z∣≥∣A∣|\mathcal Z|\geq|\mathcal A|, partition Z\mathcal Z into ∣A∣|\mathcal A| nonempty groups. Assign one action to each group, mapping uniformly within the group. Give all mediators in a group the same loss. The mediator label then gives no information about other groups, so this is a standard bandit on these groups. Similarly, for ∣A∣≥∣Z∣|\mathcal A|\geq|\mathcal Z|, partition A\mathcal A into ∣Z∣|\mathcal Z| nonempty groups, assign a distinct mediator to each group, and deterministically map all actions in the same group to its assigned mediator. This time the problem reduces to a standard bandit problem on ∣Z∣|\mathcal Z| mediator variables. Thus, for some MM, every algorithm suffers

Reg⁡T≥120min⁡(min⁡(∣A∣,∣Z∣)T,T)\operatorname{Reg}_T\ge\frac1{20}\min(\sqrt{\min(|\mathcal A|,|\mathcal Z|)T},T)

on some loss sequence (Auer et al., 2002, Theorem 5.1).

References in our response

P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput. 32(1):48–77, 2002.

T. L. Lai, H. Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6(1):4–22, 1985.

Thank you for the response.

Q3: The lower bound argument is convincing (minimax over M, not instance specific). Please add it to the paper if you haven't yet.

Q1: Since known M is standard in this literature, I see it as a limitation, not a weakness.

Q2: The new experiment is stochastic with N = 2, so it does not test the adversarial comparison. The regime where Eldowa et al. is tighter is narrow, but the bounds are not uniformly ordered, so please soften "advance both strands".

Given these answers, I have raised my score.

Reviewer_fYJ6OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper studies bandits with a known action-to-mediator mechanism, where both the sampled mediator and its loss are observed. It proposes Causal Tsallis-INF, combining the maximum of an action-space Tsallis regularizer and a calibrated mediator-space Jensen regularizer with an auxiliary action regularizer. The algorithm obtains adversarial pseudo-regret of order sqrt(min{|A|,|Z|}T) and a self-bounding guarantee whose logarithmic coefficient adapts to the smaller of action and attainable-mediator complexities. In particular, regret is constant in the stochastic case when the unique optimal action covers all reachable mediators. Synthetic, mechanism-estimation and retrospective STAR experiments assess its behavior.

Critical strengths
  1. A meaningful simultaneous guarantee. The work combines adversarial robustness with a stochastic logarithmic coefficient that adapts to action and attainable-mediator exploration costs, and obtains constant regret under support of the optimal action. Existing mediator-feedback work and ordinary Tsallis-INF supply important components, but do not directly give this combination.
  2. The key technical obstacle is addressed explicitly and the implementation is assessable. Calibrating mediator entropy at pure actions makes the maximum useful near the optimum, while the auxiliary regularizer supplies curvature when action entropy is inactive. The proofs treat negative reduced-variance estimates and supported versus unsupported mediators. The implementation checks global objective certificates. All applicable tasks in the five supplied experiment configurations completed locally without failed trajectories; the 100 declared inapplicable cells remain excluded. The complete transpose experiment appropriately isolates which complexity is favorable. The exact later 40-seed online extension was not supplied.
Critical weaknesses
  1. The literature comparison overstates the novelty of the horizon improvement. Ito, Tsuchiya and Honda (COLT 2024), Theorem 29/Proposition 16, explicitly allow stochastic expert advice: taking each expert's fixed advice to be one column of M recovers this feedback protocol and already gives a single-logarithmic stochastic BOBW bound. Dann, Wei and Zimmert (COLT 2023), Corollary 13, is a closely related EXP4-based precedent. These do not subsume the attainable-support conclusion. The specific comparison with Eldowa remains valid, but the distinctive advance should be located in the calibrated maximum and support-sensitive adaptation rather than single-logarithmic horizon dependence alone. The attainable-mediator coefficient is an upper-bound complexity; the paper does not establish a matching lower bound showing that it captures exact instance difficulty. Such a lower bound is not necessary for the current contribution to be useful.
  2. The quantitative interpretation and figure-to-theorem connection need sharpening. For the two-action channel with columns (.9,.1) and (.1,.9), mediator means (0,.1), and gap .08, direct substitution into Appendix C gives K about 738,407 for (c,alpha,rho)=(2,.75,1), or 4.714 billion at the experimental settings, versus trivial regret at most 2,400 at T=30,000. This shows certificate looseness, not poor actual performance. The main (80,30) experiment has three identical optimal actions, outside the refined theorem's uniqueness assumption; its switching regimes preserve the optimum. STAR preserves action-dependent conditional losses and supplies oracle empirical M, so its excellent numerical results are a misspecification study. The complete-graph experiment is a useful complement. Finally, the fixed optimization tolerance alone does not establish the asymptotic constant-regret guarantee for approximate iterates.
Questions for authors
  1. How do the guarantees compare explicitly with Ito et al.'s stochastic-expert result, and which improvement requires the new attainable-support geometry? Please qualify the attribution of the previous extra logarithm to entropic regularization.
  2. Can K's dependence on gaps, rare optimal-action mediator probabilities and auxiliary regularization be made more interpretable, and its finite-time usefulness separated from the asymptotic structural result? A focused example with a unique optimal action covering all reachable mediators, varying its smallest mediator probability and the horizon, would directly test the advertised constant-regret regime. This is a suggested clarification of existing claims, not a demand for a new benchmark suite.
  3. Can you correct the fallback Hessians in replication/algorithms/base/tsallis.py:442,494, state whether they affect any reported runs, and specify the regret guarantee intended under the fixed objective tolerance? Please also supply the missing PAPER_ALIGNMENT.md and VALIDATION.md referenced by the repository and reconcile the 30-seed online configuration with the later extension mentioned in its README.
2 comments
AuthorsOpenReview ↗

Response to Q1 and Q2

Q1:

We thank the reviewer for bringing up the reference to Ito et al. Indeed, the cause of the excessive log⁡T\log T factor in the stochastic bound of Eldowa et al. is the entropic regularization behind EXP4, and the work of Ito et al. shaves it off. This does not diminish the main value of our contribution, which is adaptation to the simplest of the complexities, in the action and the mediator space, as also noted by the reviewer. Similarly to Eldowa et al., the work of Ito et al. only adapts to complexity of the action space. We will add the work of Ito et al. to our comparison table (Table 1).

For an explicit comparison, the stochastic bound of Ito et al. is O(\frac{|\mathcal Z|\log|\mathcal A|}{\Delta^A_\min}\log T), whereas our stochastic bound is O(min⁡(SA,SZa)log⁡T),O(\min(S_{\mathcal A},S_{\mathcal Z}^a)\log T), where SA=∑a≠a⋆1ΔA(a)S_{\mathcal A}=\sum_{a\ne a^\star}\frac1{\Delta^A(a)} and SZaS_{\mathcal Z}^a is defined in Equation (9) and satisfies S_{\mathcal Z}^a\le\frac{|\mathcal Z\setminus\mathrm{supp}(M_{\cdot,a^\star})|}{\Delta^A_\min}, providing \min(S_{\mathcal A},S_{\mathcal Z}^a)\le\frac{\min(|\mathcal A|-1,|\mathcal Z\setminus\mathrm{supp}(M_{\cdot,a^\star})|)}{\Delta^A_\min}.

Therefore, our stochastic bound is always as tight as the bound of Ito et al., but for MM illustrated in Figures 1(b) and 1(c) there will be a large \frac1{\Delta^A_\min} and small or even zero SZaS_{\mathcal Z}^a, and thus our bound can be arbitrarily tighter. Moreover, the adversarial bound of Ito et al. is O(∣Z∣log⁡∣A∣T),O(\sqrt{|\mathcal Z|\log|\mathcal A|T}), whereas our bound is O(min⁡(∣A∣,∣Z∣)T).O(\sqrt{\min(|\mathcal A|,|\mathcal Z|)T}).

Q2:

Yes. As stated in Theorem 4.1, KK depends on M,ΔA,α,cM,\boldsymbol\Delta_{\mathcal A},\alpha,c, and ρλα\rho\lambda_\alpha, but not on TT. Theorem C.21 gives K_{\rm sb}=2K_0+\frac2{\Delta_\min}(2C_1+\frac{2\alpha C_2}{\sqrt{2\alpha-1}})^2.

Dropping the nonnegative K0K_0 and C2C_2 terms and using C1≥2Qαχ⋆/ΛC_1\ge2Q_\alpha\chi_\star/\Lambda from (49) and (52) yields K_{\rm sb}\ge\frac2{\Delta_\min}(2C_1)^2\ge\frac{32Q_\alpha^2\chi_\star^2}{\Delta_\min\Lambda^2}.

In your example, the large value is mainly due to the 8C_1^2/\Delta_\min term: C1C_1 contains the contribution 2Qαχ⋆/Λ2Q_\alpha\chi_\star/\Lambda, and closing the self-bounding argument squares C1C_1.

The gaps enter through 1/\Delta_\min, and Λ=ρλα\Lambda=\rho\lambda_\alpha enters this contribution through Λ−2\Lambda^{-2}. For full-support q⋆\mathbf q^\star, χ⋆≤1/min⁡zqz⋆−1\chi_\star\le1/\min_zq_z^\star-1, since ∑zMz,a2≤1\sum_zM_{z,a}^2\le1. Rare mediators also enter K0K_0 through t0=⌈(4vˉ⋆/Λ)2⌉t_0=\lceil(4\bar v_\star/\Lambda)^2\rceil in (49); Λ\Lambda additionally appears in C2C_2.

At c=0.7,α=2/3,ρ=0.015c=0.7,\alpha=2/3,\rho=0.015, the last expression in the displayed bound is 4.552×1094.552\times10^9, compared with Ksb=4.714×109K_{\rm sb}=4.714\times10^9 for your example. It therefore explains most of the constant's size. This limits the bound's finite-time usefulness, but not the uniform-in-TT guarantee for stochastic losses with a unique optimal action and full-support q⋆\mathbf q^\star.

Following your suggestion, we tested two actions and two mediators: the optimal action produces mediator 2 with probability q2⋆q_2^\star, while the other always produces mediator 2. We used deterministic losses ℓt=(0,1)\boldsymbol\ell_t=(0,1) or Bernoulli means μ=(0.4,0.4+0.1/(1−q2⋆))\boldsymbol\mu=(0.4,0.4+0.1/(1-q_2^\star)), giving gaps 1−q2⋆1-q_2^\star and 0.10.1, respectively. The optimal action is unique and covers both mediators. We used the parameters above and 20 seeds.

Deterministic mediator losses

q2⋆q_2^\starCausal Tsallis-INF, T=104T=10^4Causal Tsallis-INF, T=105T=10^5Tsallis-INF, T=104T=10^4Tsallis-INF, T=105T=10^5
0.40.54±0.040.54±0.0411.75±1.7017.30±1.86
0.20.77±0.080.77±0.087.98±1.0410.58±1.23
0.11.06±0.121.06±0.127.43±0.929.31±0.88
0.051.33±0.191.33±0.196.68±0.719.06±0.75
0.021.64±0.191.64±0.196.30±0.608.33±0.62

Bernoulli mediator losses, action gap 0.10.1

q2⋆q_2^\starCausal Tsallis-INF, T=104T=10^4Causal Tsallis-INF, T=105T=10^5Tsallis-INF, T=104T=10^4Tsallis-INF, T=105T=10^5
0.42.17±0.942.17±0.9437.97±5.2453.63±6.60
0.23.62±0.883.62±0.8840.01±4.1056.34±4.94
0.18.70±1.908.70±1.9038.42±3.8155.04±4.11
0.0514.59±2.9414.59±2.9440.14±5.0456.56±5.10
0.0222.11±5.1122.11±5.1136.87±4.3852.69±4.28

Entries report the mean ± standard error of ∑t=1TΓ(pt)\sum_{t=1}^T\Gamma(\mathbf p_t) over 20 runs. Causal Tsallis-INF plateaus at the displayed precision, while Tsallis-INF regret increases in every row. The plateau rises as q2⋆q_2^\star decreases. We will add these results to the appendix.

AuthorsOpenReview ↗

Response to Q3

Q3: Thank you for checking the code. We removed obsolete references to PAPER_ALIGNMENT.md and VALIDATION.md, which were consistency and implementation notes; public documentation and tests provide the experiment specifications.

For online mechanism estimation, we ran 30 repetitions per condition for all three dimension pairs, then 10 more for (∣A∣,∣Z∣)=(30,80)(|\mathcal A|,|\mathcal Z|)=(30,80), with unchanged qualitative conclusions.

Neither affected fallback activated in 60 diagnostic runs, covering known/estimated mechanisms, stationary/baseline-switching losses, and random/graph-based mechanisms. We corrected both Hessians by removing the extra α\alpha factor.

Our guarantees, like the competitors', assume exact minimizers. Numerical-error analysis is outside our scope; experiments demonstrate good practical performance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.