Improved Regret Bounds in Stochastic Contextual Bandits with Graph Feedback

Q: The paper is not very well structured

A: Thanks for suggestions. To help readers understand our work better, we add the name of graph parameters in the caption of tables. We also show the order sequence of this graph parameters to highlight our contributions. As for ``a simplified version of main theorem'', we will try to put it in our work if there exists additional space. After all, the limited page requirement of ICLR forces us to put formal descriptions in the following sections.

Q: it does not seem necessary to present ConstructExplorationSet with two options

A: Our main contribution stems from the second option. However, the first option is not always useless, as in certain types of graphs like perfect graphs, it can outperform the second option. The two options also capture the trade-off of the exploration between the gaps and number of actions. Additionally, the first option can be served as a rough realization of the method in [1] as their regret order scales with the independence number.

Q: the contribution comes more in the proof aspects

A: It requires non-trivial modifications of IGW technique. The time-varying hyperparameter $\gamma_t$ and the adaptive set $S_t$ are the crucial difference of original works. The original works focus on the upper bound so they only need an upper bound $|\mathcal{A}|$. In order to capture the influence of time-varying action sets, we have to bound the size of action sets in a more refined way. It requires us to define the policy space and prove lemmas in a more refined way.

Here is the high-level intuition of our proof. For any policy $\pi \in \Psi(S_t)$, the regret of $\pi$ with respect to the greedy policy can be controlled by our lemma B.1. Secondly, since the sample size will increase as the learning processes, the regret of the greedy policy with respect to the optimal policy will become smaller, as shown in lemma B.2. Due to these two lemmas, the policy $\pi \in \Psi(S_t)$ can be controlled.

Q: the high-probability bound to the expected bound

A: It can be converted to expected bounds by setting $\delta=1/T$.

Q: Technically, in Tables 1 and 2, results of Wang et al.2021 can be presented with upper-bound of $\alpha(G_t)$ and hence, only require to know this upper-bound instead of the real independence number. This mitigate the "critics" in page 4.

A: You are correct, but the original content in their work write in the form of $\alpha(G_t)$.

Q: Do the authors choose to run experiments only in comparison with FALCON and not the one of Zhang et al. 2023 because the latter is instable?

A: We appreciate the Zhang's work[1], which firstly deals with the general function space, but their method need online regression oracle and works in semi-adversarial setting. However, our method only requires offline regression oracle and works in stochastic setting. For one thing, the adversarial setting is more difficult than the stochastic setting. It usually happens that the algorithms for adversarial settings will have worse regrets than those in the stochastic setting. For another, the online oracle is more difficult to design than the offline oracle. Online oracle is sensitive to the order of input data sequence while offline oracle not. Even for a fixed dataset, the input sequence will also affect the output of online oracles. As an example, the OLS estimator is a valid offline oracle but not a valid online oracle.

To see our efforts, we refer the reviewers to option 1. Roughly speaking, the option 1 can be viewed as the realization of this method, though not fully identical. We try to find effective baselines and compare them in theory and simulations.

Q: The presented framework uses undirected feedback graph, can this be extended with directed ones? (note that Zhang et al. consider directed graph).

A: This is an interesting work to extend our method to general graphs. However, as we admit in the conclusion section in Appendix D, we haven't find a way to deal with general graphs.

Q: Can we have a definition of the set $S_t$?

A: The name of $S_t$ is called the exploration set.

[1] Practical contextual bandits with feedback graphs

Q: the forced exploration and the construction of the exploration set $S_t$

A: The forced exploration is necessary to avoid suboptimal greedy policy. We need to control the size of the exploration set to reduce regret order.

Q: UCB-like approach

A: It is widely known that UCB can achieve comparable performance with sampling method. However, it is unclear how one can build valid confidence upper bounds on general function space. It is also unknown whether one can truncate the action set as we do. To point out the challenges, the previous works [1,2,3] about general function space all focus on IGW rather than UCB.

[1] Practical contextual bandit with regression oracle [2] Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability [3] Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective

Q: Fundamental importance of $\delta_f(G)$

A: This is a crucial factor in stochastic graph feedback setting, which dates back to [1]. It control the minimal size of arms which should be explored. Such factor can be obtained by solving LP

$

\begin{aligned}
& \min \mathbf{1}^\top \mathbf{z} \\
\text{s.t.} \ \ \ & G_t \mathbf{z} \geq \mathbf{1} \\
& \mathbf{z} \geq \mathbf{0}.
\end{aligned}

$

The LP can be interpreted as following. If one want to explore all arms at least once, how many arms should one pull given the graph $G$. The LP can help control the number of exploration in a most efficient way. The appearance of this factor in upper and lower bounds[1,2] also show its importance in analysis.

[1] Reward maximization under uncertainty: leveraging side-observations on networks [2] Contextual bandit with side-observations

Q: It would be beneficial to have real-world examples that align with the setup described in the paper. Specifically, are there tangible instances where the function class and changing graphs over time can be observed?

A: We haven't found any open dataset which fully fit our setting. Though we can conduct experiments in real-world datasets, what we obtain is a regret curve. To illustrate the basic property, we believe that the randomly generalized contexts and graphs are enough.

Q: Theorem 3.1's phrasing presents a contradiction. On one hand, it mentions that the "expectation of regret is taken w.r.t. all kinds of randomness," but then goes on to state the result is "with high probability." What is the specific randomness associated with the high probability argument, and how does it differ from the randomness tied to the expectation? Could you clarify this split?

A: Thanks to point out our typos. The expectation is taken with respect to the randomness of algorithms. If one wants to get the expected regret bounds, one can simply set $\delta=1/T$ and it only leads to additional $\delta T$ regrets, which is a constant.

Q: Regarding Theorem 3.2, how expansive is the function class? Are there any practical applications or examples that fall within these classes that can provide a clearer context?

A: Theorem 3.2 provides a lower bound. Typically, such bound is proved by construction to show the difficulty level of this problem. If one cares about practical applications, the gap-dependent upper bound in Theorem 3.3 might be more meaningful, as it holds for general gap $\Delta$ and general function space $\mathcal{F}$.

Q: In the simulations section, is it feasible to use the baseline of algorithms from related works for comparison? This would offer a more holistic view of how the proposed methods stack up against existing solutions.

A: For our mentioned works, their settings are not fully identical to us. [1] works in MAB with fixed graphs. [2] works for linear contextual graphs with fixed graphs. [3] deals with the general function space, but their method need online regression oracle and works in semi-adversarial setting. However, our method only requires offline regression oracle and works in stochastic setting. Roughly speaking, the option 1 can be viewed as the realization of this method, though not fully identical. To compare them effectively, we have to illustrate the theoretical properties of this work in Table 1.

[1] Reward maximization under uncertainty: leveraging side-observations on networks [2] Contextual bandit with side-observations [3] Practical contextual bandits with feedback graphs