Summary
In this research, the authors investigate the concept of Nash regret in the context of stochastic linear bandits. Nash regret represents the disparity between the optimal reward and the geometric mean of expected rewards, reflecting fairness considerations across different time instances within the Nash social welfare framework. The study assumes a fixed set of arms denoted as $\mathcal{X}$, and an unknown vector $\theta^*$. When an arm x is chosen, the agent observes a sub-Poisson $r_t$ with a mean of $<x,\theta^*>$. The nash regret is defined as $max_x<x,\theta^*>-(\prod_t \mathbb{E}[<X_t,\theta^*>])^{1/T}$ where $X_t$ is a selected arm at time t.
To minimize Nash regret, the authors propose an algorithm that incorporates elimination phases. Firstly, to ensure the lower bound of expected rewards, they employ sampling via the Jon ellipsoid technique, as in Lemma 4. Additionally, they employ a G-optimal design to construct a probability distribution over arms, aiming to minimize the confidence interval width of estimated rewards. By combining these strategies, a sequence of arms is generated, and elimination phases are employed to remove arms with suboptimal mean rewards, utilizing upper confidence bounds (UCB) and lower confidence bounds (LCB) with a doubling time horizon for exploration.
To construct the UCB and LCB, a Nash confidence bound is utilized, which contains the mean reward value. Larger mean rewards correspond to larger confidence intervals, as defined in equation (8).
The theoretical analysis demonstrates that for a finite number of arms, the proposed algorithm achieves a nash regret of approximately $\tilde{O}(\sqrt{d/T})$. In the case of an infinite number of arms, the regret is $\tilde{O}(d^{5/4}/\sqrt{T})$ with a modified confidence width.
Strengths
- This paper addresses the concept of nash regret in the context of stochastic linear bandits.
- It presents a novel algorithm based on elimination phases and provides a detailed regret analysis.
Weaknesses
- The paper does not discuss the computational aspects of finding the G-optimal distribution and sampling via the John ellipsoid method.
- It does not include experimental results.
- In the case of infinite arms, the achieved regret bound may not be sufficiently tight, as it involves a factor of $d^{5/4}$ instead of just $d$.
Questions
- I'm wondering what is the reason for using an elimination-based algorithm rather than UCB.
- wondering what is the reason to consider sub Poisson distribution rather than sub gaussian.
- In line 504 (proof of Theorem 1 in appendix), when $\langle x^*,\theta^* \rangle\le \sqrt{d\nu/T}$, what is the reason that the NR bound, which contains $\langle x^\star,\theta^\star \rangle$ in the bound, trivially holds?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
- This problem deals with a fixed arms set rather than a contextual linear setting.
- The regret bound of $d^{5/4}$ in the case of infinite arms may not be tight, and it would be better to elaborate on why the factor of $5/4$ appears. ( $\sqrt{d\log|\mathcal{X}|}$ regret bound for the finite case seems to imply $d$ when we consider $|\mathcal{X}|=2^d$ for infinite case.)
- There are no experimental results and discussion on the computational cost, which raises concerns about practical aspects
Minor comments:
- line 441 in Appendix: $d$-> $\sqrt{d}$
- line 449 in Appendix: $\langle x,\hat{\theta}\rangle \le 20$ --> $\langle x,\hat{\theta}\rangle \ge 20$
- Lemma 7, equation (10) in Appendix: $P()\le 4T^{-1}\log T$ -->$P()\ge 1-4T^{-1}\log T$ ?