Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits

Concerning dependance in $T$

The log(T) term has a power 3 in the regret bound, which can be improved. Do you think the $\log(T)^3$ factor can be reduced ? Why is there such a factor, whereas usually there is simply a $log(T)$ factor ? A sharp dependence on the horizon $T$ is more important for the instance-dependent guarantees.

The $\log(T)$, actually has a power $2$ for OLS-UCB-C and $3$ for COS-V. The two first exponents come from the online nature of the problem (Laplace trick) and the covariance estimations. The last one, only present in COS-V, comes from the union bounds made on the sampling distribution.

ESCB-C manages a $\log(T)$ with power $1$, but suffers from more computational complexity than OLS-UCB-C and does not satisfy a $\tilde{O}(\sqrt{T})$ gap-free regret because it incurs a $1/\Delta_{min}^2$ in the gap-dependent bound. For randomized algorithms, there exists $\log(T)$ gap-dependent bounds for Combinatorial Thompson Sampling. However, they also suffer from additional terms that can be up to $1/\Delta^d$, which prevent the $\tilde{O}(\sqrt{T})$ gap-free bound.

All in all, it is indeed possible to get better $\log(T)$ exponents for the gap-dependent bounds. However, known approaches do not satisfy a $\tilde{O}(\sqrt{T})$ gap-free bound at the same time. It means that on “difficult" instances, our algorithms will incur $\tilde{O}(\sqrt{T})$ regret, while others may suffer regrets that are a lot worse (Imagine $\Delta \sim 1/T$ for example).

We are not aware of any straightforward way to reduce the $\log(T)$ exponents and keep the desired gap-free bounds at the same time.

Concerning the covariance matrix

The approach of estimating the covariance matrix online and using it for confidence bounds is not new.

The approach is indeed not new (and it is even natural) and we do not claim to be the first. But the way to incorporate those estimators in our analysis is rather new.

I read the authors’ rebuttal and the comments of other reviewers. I would like to keep my score unchanged.

Concerning the weaknesses

The assumption that the reward (Lines 45-46) for each base item ($Y_{t,i}$) is bounded by ($\frac{B_i}{2}$) may be strong, where reward distributions can exhibit significant variability and are not tightly bounded.

In many realistic settings, a player would be able to tell what scale of values for $Y_{t, i}$ is normal or not. If they can identify an upper bound $B$, then they could use the algorithms with $min(max(Y_{t, i}, -B), B)$ instead of the "true" $Y_{t, i}$ observed.

Otherwise, one could try a Doubling Trick. We initialise $B$ at a certain power of $2$, and then we restart the algorithm each time an observation surpasses it, after doubling the current value of $B$. This would add a multiplicative factor to the regret bounds, of magnitude $\log(B)$, where $B^*$ is a “true" upper bound.

Concerning the main questions

Concerns regarding the role of $f_{t,\delta}$ and $g_{t,\delta}$ functions in Eq. 6 and 7. The algorithms utilize the functions $f_{t,\delta}$ and $g_{t,\delta}$ to dynamically adjust the exploration strategy. The paper implies an increase in $f_{t,\delta}$ and $g_{t,\delta}$ as $t$ increases, which leads to an increasing exploration bonus and variance over time. [...]

a) Increasing Exploration Over Time [...].
b) Design Justification for $g_{t,\delta}$ and $f_{t,\delta}$ [...].
c) Impact on Algorithm’s Performance [...].

We acknowledge the fact that the $\log(t)$ increase can be counterintuitive and may add an explanation in subsequent versions to clarify it.

The exploration is actually not increasing over time. The decay on the exploration bonus, comes more from the number of times each item/couple has been observed $(n_{i,j})$ rather than from $\log(t)$ (See Eq.4 and Eq.6 for example). Like for all the main variants of UCB, the exploration bonuses look like a sum of $\sqrt{\frac{\log(\delta)}{n_{i,j}}}$, which decreases as the number of time each item is chosen increases.

Using $\log(t)$ (instead of $\log(T)$) ensures adaptivity to the time horizon and has been commonly used in several other papers.

The justification for $f_{t, \delta}$ is explained in Section 4: it originates from the way the ellipsoids are designed. $f_{t, \delta}$ is involved in the definition of event $G_t$ in Eq.9 and its expression ensures Prop.1 is satisfied. $g_{t, \delta}$ controls the exploration made by COS-V. Its expression is derived from union bounds which enable Lemma 5 to be satisfied.

The paper specifies using a Gaussian distribution in Eq. 7 for parameter sampling within the COS-V algorithm. Could the authors provide further justification for the choice of a Gaussian distribution in this context?

We think that other distributions could actually be used.

Using Gaussian distributions was a natural direction as they are standard distributions, we know how to sample them efficiently, especially for given covariance matrices, and we know how to control their tails with usual tools.

Thank you for the response from the authors.

1. I have reviewed the experiments conducted by the authors, and I am particularly curious about the regret pattern of OLS_UCBV, which shows a distinct zigzag shape: it starts with a slow increase in regret, followed by a sharp rise, and then it tends to converge. This has also piqued my curiosity about the specific settings of the randomly generated synthetic environment, and it appears that its results are inferior to those of C_UCBV and ESCB_C_approx.

2. Additionally, if it is Covariance-Adaptive, I would like to know how the fluctuations or error bars of the actual performance of the algorithm proposed by the authors compare to those of other algorithms across multiple random seeds.

Concerning the minor questions and remarks

We first wish to thank the reviewer for pointing out our typos and inaccuracies.

Be more precise in the formulation of the lower bound (Thm. 2): In which sense does the inequality hold, in expectation? Also, is policy restricted deterministic policies here?

The theorem holds in expectation, and is applicable for both deterministic and for stochastic policies.

Besides, it seems that there is a mistake in our formulation. We inverted a “for all" and a “there exists" statement. We should have written: “For any policy $\pi$, there exist a stochastic combinatorial semi-bandit such that$\dots$". We are very grateful to the reviewer for pointing out this inaccuracy, which allowed us to correct a mistake.

In Algo.2, line 3, does it have to be $\leq 2$ instead of $\leq 1$ ?

It should be either $\leq 1$ or $<2$. All the coefficients indexed by $(i,j)$ are correctly defined as soon as the corresponding interaction has been observed at least twice.

You oftentimes write $A\bigcap B$ instead of $A\cap B$, why?

The reason is purely aesthetic, we will uniformize the notation.

Concerning the main questions

Do you have a feeling how sensible the regret is w.r.t. the vector $B$? You assume this to be known, but I could imagine that in practice it's oftentimes unknown.

In our analysis, $B$ appears in the negligible additive terms (w.r.t. the dependence in $T$). Using a “looser" $B$ may make the convergence a little slower, but would not impact the asymptotic regret.

In practice, knowing a plausible upper bound on the rewards is sufficient. In realistic settings, we can assume that a player knows such an upper bound B_i. In that case, they can replace $Y_{t, i}$ with $min(max(Y_{t, i}, -B_i), B_i)$ and use our algorithms.

Otherwise, one could try a Doubling Trick. We initialise $B$ at a certain power of $2$, and then we restart the algorithm each time an observation surpasses it, after doubling the current value of $B$. This would add a multiplicative factor to the regret bounds, of magnitude $\log(B^*)$ where $B$ is a “true" upper bound.

In Table 1, do you know how $C^{opt}_{1/T}$ scales in comparison to $d^2$ ? That is, do you know that OLS-UCB-C outperforms ESCB-C regarding time complexity?

$C^{opt}_{1/T}$ scales with the horizon $T$, contrarily to ou per-rounds complexities. Ultimately, our complexity will then be better for horizons large enough.

Both your algorithms have a parameter $\delta>0$, which is not contained in the upper bounds. Could you say how the behaviour of the regrets are w.r.t. this parameter?

We have formulated $f_{t, \delta}$ and $g_{t, \delta}$ so as to isolate $\delta$ from the dependence on time and dimension.

Its influence shows through $\log(1/\delta)$ factors in negligible additive terms. $\delta$ is fixed at the beginning and characterizes a tradeoff when sizing the ellipsoids. It influences how quick we reach the asymptotic regret rate but not the said rate.