Bandits with Preference Feedback: A Stackelberg Game Perspective

Summary

This paper considers bandits with preference feedback. It first constructs a novel confidence set that covers the ground truth with high probability. Then from a Stackelberg game perspective, it proposes an efficient algorithm that enjoys tighter regret bound than SOTA.

Strengths

1. The technique used to construct the confidence set is interesting. The resulting confidence set is tighter. 2. The Stackelberg game perspective is interesting, and allows the author(s) to design the algorithm with better exploration-exploitation trade-off as demonstrated in the experiment.

Weaknesses

The major concern is the practical applicability of the algorithm. Seems that the proposed algorithm can hardly scale up to a higher dimension (e.g., dimension equals to 7). In the proposed algorithm, a complicated sequential optimization problem needs to be solved. Notably, the experiment only considers two-dimensional problem, in sharp contrast to recent works (e.g., 12-dimensional problem considered in Xu et al. [2024]).

Questions

1. In the abstract, the review claims that the regret bound is 'rate-optimal'. Is there a matching lower bound? 2. Can the results be generalized to other link functions? 3. In line 168, should it be $\sup_{|a|\leq B}$ instead of $\sup_{a\leq B}$? 4. Could the authors explain the linear growth of multiSBM in Fig. 1 (b)?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Some major comments: 1. The paper discusses the comparisons to [Xu et al. 2024]. Seems that the theoretical gain of $T^{\frac{1}{4}}$ mainly comes from tighter confidence set rather than the design of the algorithm. If the algorithm POP-BO in [Xu et al. 2024] is equipped with this tighter confidence set, it could also achieve the same regret bound. To see which algorithm is empirically better, it would be interesting to compare the proposed algorithm with POP-BO equipped with the tighter confidence set in this paper. Besides the points mentioned above, here are some minor comments: 1. In line 109, I guess it should be {$0, 1$} instead of $[0, 1]$. 2. In line 178 to 179, typo in "ridge estimator estimator". 3. In line 574, abuse of the notation $s$.

Summary

This paper considers novel game-theoretic acquisition function for pairwise action selection with preference feedback. It is tailored to the setting with infinite domains and nonlinear kernelized rewards. The preference-based confidence sequences for kernelized utility functions are shown to be tight and anytime valid. The proposed algorithm MAXMINLCB is shown to satisfy a sublinear regret. Various simulations were conducted to showcase the advantage of the proposed method.

Strengths

1. Although preference-based bandit optimization with linear utility functions is fairly well understood, such approaches cannot capture real-world problems with complex nonlinear utility functions. This paper aims to close this gap. The considered problem is timing and interesting. 2. The technical contribution is non-trivial. Although there have been attempts to prove convergence of kernelized algorithms for preference-based bandits, such works employ a regression likelihood model which requires them to assume that both the utility and the probability of preference lie in an RKHS. Moreover, a sample-efficient algorithm is lacking for such approaches. In contrast, this work uses a kernelized logistic negative log-likelihood loss to infer the utility function, and provide confidence sets for its minimizer. 3. Some theoretical result, like Kernelized Logistic Confidence Sequences in Theorem 2, is also of independent interest. 4. In spite of a theoretical paper, it is well written and is easy to follow.

Weaknesses

1. In practice, how to determine the hyper-parameters like $\gamma_t$, $L$, and $B$ in (5)? Is there any data-driven way to select them? 2. In the main Theorem 6, the regret bound is $\gamma_T^{D}\sqrt{T}$. The term $\gamma_T^{D}$ is the T-step information gain of kernel, which is also a function of $T$. The authors claim that this rate improves that of Xu et al. (2024) by a factor of $T^{1/4}$. However, the cumulative regret bound in Theorem 5.2 of Xu et al. (2024) is of a similar order. Xu et al. (2024) also provided explicit regret upper bounds for various common kernels in Theorem 5.5. Hence, it is also interesting to provide an explicit form of $\gamma_T^{D}$ for some common kernels, and to compare these regret upper bounds in a fair way. 3. In Figure 1, the authors presented the result for the Ackley function, which shows a clear advantage of the proposed method. However, in more extensive simulations (e.g., Matyas function in Figure 6, ) in the appendix, the proposed method is outperformed by the competitors. It is helpful to provide some discussion on these results, and offer some insights on when the proposed method would work well. This is helpful for practitioners.

Questions

see Weakness

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

The paper examines the problem of bandit optimization with preference feedback in large domains and nonlinear (kernelized) rewards. It introduces MAXMINLCB, which adopts a game-theoretic approach to action selection under comparative feedback. Additionally, it proposes kernelized preference-based confidence sets, which can be utilized in related problems.

Strengths

(1) Rather than jointly selecting the arms in dueling bandits, the proposed method jointly optimizes both actions by choosing them as the equilibrium of a two-player zero-sum Stackelberg game. This approach enables a more efficient exploration/exploitation trade-off. (2) The regret guarantee presented in this paper is tighter by a factor of $T^{1/4}$ compared to Xu et al. (2024).

Weaknesses

(1) Although the paper uses a kernelized logistic model to approximate the rewards, this approach may remain too simplistic for capturing the complexity of rewards in real-world applications. (2) The paper lacks a comparison in the experiments with the related work by Xu et al. (2024). (3) In real applications, it is more common to rank between two state-action pairs. However, the paper does not consider contextual information and solely focuses on the multi-armed setting, which is less interesting and useful.

Questions

(1) Can you implement the algorithms compared in Section 6.2 using the original confidence sets from the references? (2) Can this work be extended to contextual bandits with preference feedback?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

Please see weaknesses.

Summary

This paper considers bandit optimization with preference feedback over continuous action spaces and kernelized reward function. The goal in this problem is to minimize the dueling regret against an optimal action over a finite time-horizon. Previous works on this problem are either restricted to finite action spaces or linear reward functions. The proposed algorithm casts the problem as kernalized logistic regression and designs confidence sets for the relative preference between two actions. It then proposes an action selection strategy based on a game theoretic Leader-Follower formulation that utilizes these confidence intervals. The paper provides a regret bound as well as empirical evaluation for the proposed algorithm.

Strengths

The main contributions of the paper are two-fold: 1. Expanding the existing literature on dueling bandits by studying kernelized reward functions under infinite and continuous action sets. This requires new techniques to bound the confidence intervals. 2. Proposing a principled game-theoretic approach to action selection in dueling bandits that can be of further interest. In my opinion these are two important contributions to the literature. Since these ideas are likely to be relevant to other learning problems with preference feedback such as RLHF, I think that the results in this paper have a good scope. The paper is well-written and the contributions are clear.

Weaknesses

Experimental evaluation can include other algorithms that are known to perform better than RUCB such as RMED (Komiyama et al., 2015) and Double Thompson Sampling (Wu and Liu, 2016).

Questions

It would be interesting to see if the current approach can be extended to other link functions beyond the sigmoid such as probit.

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

The paper can include a section of limitations of the current work in terms of social impact.

thanks for the clarification

the authors' clarification is helpful. I do not have any additional question and would like to maintain my rating.