Conservative Contextual Bandits: Beyond Linear Representations
Contextual Bandits;Safety;Neural Bandits;Constrained Bandits
Yes
No ethics review needed.
Some clarification questions apart from the concern in Weaknesses:

- Data-dependent bound
  - When $L^*=O(1)$, it seems the regret bound becomes $\tilde O(\ln T)$. Is there any instance-dependent metric (similar to the mean gap in the stochastic MAB setting) hiding in the constant term?
  - $\gamma_t$ seems to be requiring the knowledge of not only $L^*$ but also each component that sums up to $L^*$. Would that be too strong?

- Experiments
  - Can you provide more details on how you set $\delta$ and tune hyperparameters? How do you run C-FastCB if the optimal cost is not known?

- Typos:
  - Algorithm 2 Line 8: Is there a term related with $\sqrt{\log\delta^{-1}}$ missing?
  - Line 836 missing a sqrt term consisting of $m_{\tau-1}$ and $\texttt{Reg}$.
- The paper is clearly written and mostly easy to follow, with proof roadmap and intuition moderately provided.
- The provided solution nicely connects safe conservative bandits and contextual bandits with general functions class.
- Analysis is sound and rigorous. Numerical experiment is convincing.
This authors consider Conservative Contextual Bandits with general value function class and develop two algorithms C-SquareCB and C-FastCB, using Inverse Gap Weighting and online regression oracles. They show that the safety constraint is satisfied with high probability (the performance is not worse than a baseline policy by more than $(1+\alpha)$ factor). They also show the regret for C-SquareCB is $\tilde O(\sqrt{KT}+K/\alpha)$ and the regret for C-FastCB is $\tilde O(\sqrt{KL^*}+K/\alpha)$, where $L^*$ is the cumulative loss of the optimal
policy. The efficacy of the proposed algorithms is validated on real-world data.
As a paper that combines two established sub-fields in bandits, it is a bit unclear the novelty in algorithmic design and theoretical analysis. I would like to see authors provide and emphasize more detailed discussions if possible. In particular, what is your technical/methodological contribution compared to Kazerouni et al. (2017), Foster & Rakhlin (2020), Foster & Krishnamurthy (2021)? What are the challenges of adapting/extending their tools? From what I understand, the novelty appears in: a delicate safety criterion and a time-varying exploration schedule. The authors can add more if necessary.
Yes
No ethics review needed.
In Definition 2.2, line 124, alpha is chosen to be <1. I’m wondering if this is just a simplifying assumption, or there is difficulty in extending the results of this paper to settings where alpha>=1? 

In line 160, what is H in the ``inf’’?
The paper is overall well written, with clearly presented problem formulations, algorithms and results. The setup considered fills in the gap of current conservative bandit literature, and the proposed algorithms have provably sublinear (in T or L*) regret while being (1+alpha) competitive against the baseline. Experiments further demonstrate their superior performance as compared to algorithms designed for conservative linear contextual bandits and for classical settings without baselines.
The paper studies the conservative contextual bandit problem, where the goal is to minimize the regret as in classical contextual bandit problems and, with high probability, be competitive against a baseline policy. Importantly, the cost functions are not assumed to be linear in the contexts. This extends previous study of conservative bandit problems beyond the multi-armed setting and the contextual linear setting. 

The two proposed algorithms, C-SquareCB and C-FastCB, combine the inverse gap weighting based exploration and online regression oracles (e.g. function approximation using neural network+ gradient descent), and achieve regret which is sublinear in the horizon T or sublinear in the optimal loss L*, while being (1+alpha)-competitive against the baseline with high probability. Experiments using real world data show that C-SquareCB and C-FastCB have smaller regret compared to algorithms for contextual linear bandit problems, and are more competitive against the baselines.
The proofs/assumptions may lack rigor. In particular, the proofs cite results in other works without carefully checking the assumptions under which those results hold. For instance, in line 914-915, lemma 2 in Foster & Rakhlin (2020) is invoked. If my understanding is correct, that lemma requires Assumption 3 to hold for all possible sequences. Nevertheless, in line 1736-1737, Assumption 3 is only proved to hold with high probability. 

One contribution of the work is to use neural network for function approximation to deal with the non-linearity in the cost functions. However, to achieve the stated performance as in Theorem 5.2, the width (and thus the number of parameters) of the neural network is Omega(poly(T)), which might be too large for long-horizon problems, making the algorithms less practical. 

The paper could benefit from more detailed discussion on the significance of the regret bounds in Theorem 3.1 and Theorem 4.1. In particular, it appears that for any algorithm which has regret upper bounded by alpha * y_l * t, under Assumption 2, equation (2) is automatically satisfied. Some discussions on the range of parameters might help the readers better understand the significance of the results.
Yes
There are no specific ethics concerns.
No ethics review needed.
1. In Algorithm 1, if the safety condition is not met, the baseline policy ($b_t$) is used, and its noiseless cost $h(x_{t,b_t})$ is observed. However, this data is not used in the oracle. Since the baseline policy provides high-quality data with zero noise, why is it not utilized? Would using this data yield a better estimator? Additionally, in the linear cost case (Kazerouni et al., 2017), a noisy reward is observed for actions chosen by the baseline policy (e.g., $y_{t,b_t}$). What would happen if, in this paper’s setting, the algorithm observed $y_{t,b_t}$ instead of $h(x_{t,b_t})$?

2. The algorithm introduced in Section 4 is referred to as having a “first-order regret bound.” Why is it called “first-order”? How would second-order and third-order bounds be defined?

3. When defining the Neural Tangent Kernel (NTK) matrix, is $x_t$ the feature chosen by the algorithm at time $t$? If so, it seems unclear how the NTK can be defined given that the chosen features are unknown prior to starting the algorithm. It may be better to define the NTK matrix based on the context of all actions at all times, as in Zhou et al. (2020). Additionally, the regret bounds in Theorems 5.1 and 5.2 are independent on $\lambda_0$. Why is this assumption necessary, and does it not affect the regret bound?

4. Most literature on Neural Tangent Kernel-based neural bandits shows a dependency of regret on the effective dimension of the NTK. In contrast, the proposed paper presents a dependency on $K$ instead of the effective dimension. Could you explain what enables this distinction?

5. In the Neural Conservative Bandit, the activation function in the first-order bound changed from a smooth & Lipschitz function $\phi$ to a sigmoid function $\sigma$. What are the differences between $\phi$ and $\sigma$?

6. There do not appear to be terms related to the perturbation constant or the number of ensemble $S$ in the regret bound. Do these quantities not affect the regret? Additionally, how are these hyperparameters chosen in the experiments, and how do they impact performance?

---

**[Typo]**

- line 295: “Line 7” should be “Line 8.”
- The proposed algorithm introduces the first conservative contextual bandit algorithm for a general reward model by adapting the assumption of access to a regression oracle and leveraging the IGW algorithm, which previously applied only to linear reward models. The authors also present regret analysis for the algorithm. Although I was unable to rigorously verify all proofs, the results appear consistent, achieving a regret bound comparable to that of the linear case.  
- The methodology is illustrated with examples using an online gradient descent regression oracle and feed-forward neural networks. Real-world data experiments further support the algorithm’s performance.
This paper proposes algorithms for the conservative contextual bandit problem under a non-linear reward model.  The proposed algorithms apply IGW exploration based on an online regression oracle, enabling the selection of either an exploratory or a conservative policy based on a safety condition.  The proposed algorithms achieve sub-linear regret with respect to the total time step $T$, and its performance is supported by numerical experiments.
1. This paper introduces multiple algorithms and theoretical results for the conservative contextual bandit problem with a general non-linear cost function. Consequently, much of the main content is focused on the operation of the algorithms, assumptions required for the theoretical results, and descriptions of the outcomes, with limited discussion of the technical challenges arising from handling non-linear cost functions in CCB and how these challenges were addressed. It seems that Algorithm 1 and Algorithm 2 are almost identical aside from the use of different regression oracles. Moreover, if, as the authors state, Algorithm 2 has a tighter regret guarantee than Algorithm 1, it may be beneficial to focus more on Algorithm 2, detailing the challenges and technical novelties associated with it.

2. The main theorem statements lack completeness. For example, in the statement of Theorem 3.1, there is no indication of how to set the input parameter $\gamma$ for the algorithm to achieve the stated regret bound. Similarly, Theorem 5.1 could benefit from more precise language rather than vague expressions like “appropriate choice of parameter”. Additionally, based on my understanding, the exploration parameter $\gamma_i$ in Algorithm 2 appears to depend on $\eta_i$ (line 1218). However, $\eta_i$ in turn depends on $L_i^*$, which is the true cost value of the optimal action and unknown to the agent. Further clarification is needed on how $\gamma_i$ is determined.

3. The description for experiment reproducibility is lacking. Additional information, such as how the hyperparameters for each algorithm are set, would be helpful.
Algorithms for safe exploration in Conservative Contextual Bandits, ensuring performance stays within a safe range of a baseline policy for general non-linear costs.
@inproceedings{
anonymous2024conservative,
title={Conservative Contextual Bandits: Beyond Linear Representations},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=SThJXvucjQ},
note={under review}
}
Conservative Contextual Bandits (CCBs) address safety in sequential decision making by requiring that an agent's policy, along with minimizing regret, also satisfies a safety constraint: the performance is not worse than a baseline policy (e.g., the policy that the company has in production) by more than $(1+\alpha)$ factor. 
Prior work developed UCB-style
algorithms for this problem in the multi-armed (Wu et al., 2016)  and contextual
linear (Kazerouni et al., 2017) settings.
However, in practice the cost of the arms
is often a non-linear function, and therefore existing UCB algorithms are ineffective in such settings. 
In this paper, we consider CCBs beyond the linear case and develop two algorithms $\mathtt{C\text{-}SquareCB}$ and $\mathtt{C\text{-}FastCB}$, using Inverse Gap Weighting (IGW) based exploration and an online regression oracle. 
We show that the safety constraint is satisfied in high probability and that the regret for $\mathtt{C\text{-}SquareCB}$ is sub-linear in horizon $T$, while the the regret for $\mathtt{C\text{-}FastCB}$ is first-order and is sub-linear in $L^*$, the cumulative loss of the optimal policy. 
Subsequently, we use a neural network for function approximation and online gradient descent as the regression oracle to provide $\tilde{\mathcal{O}}\big(\sqrt{KT} + K/\alpha\big) $ and $\tilde{\mathcal{O}}\big(\sqrt{KL^*} + K (1 + 1/\alpha)\big)$ regret bounds respectively. 
Finally, we demonstrate the efficacy of our algorithms on real world data, and show that they significantly outperform the existing baseline while maintaining the performance guarantee.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Contextual Bandits Safety Neural Bandits Constrained Bandits
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/2e7be07c0ecdf4bca699de15a3683996ff6c067b.pdf
reinforcement learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/7dace878088a6cd9128db57deb4ad419979c0137.zip
Conservative Contextual Bandits: Beyond Linear Representations
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission