Summary
The paper addresses the problem of adversarial linear contextual bandits, where loss vectors are selected adversarially and the context for each round is drawn from a fixed distribution; traditional approaches require access to a simulator for generating free i.i.d. contexts or achieve a sub-optimal regret no better than $\widetilde O(T^{5/6})$.
The authors significantly improve on these methods by achieving a regret of $\widetilde O(\sqrt{T})$ without the need for a simulator, while maintaining computational efficiency when the action set per round is small. The results affirmatively answer an open question about the existence of a polynomial-time algorithm with $\mathrm{poly}(d)\sqrt{T}$ regret. The approach allows for the case where the loss is linear up to an additive misspecification error, showing a near-optimal dependence on the magnitude of this error.
The paper also presents a computationally inefficient algorithm that provides an improved $\widetilde O(d\sqrt{T})$ regret without a simulator, expanding on the EXP4 algorithm.
Strengths
The paper presents an algorithm that innovatively instantiates an individual Follow-The-Regularized-Leader (FTRL) algorithm on each action set. This development has a wide range of implications for fields. It promises more efficient and effective optimization algorithms in the face of adversarial environments.
One of the major strengths of the paper lies in the construction of loss estimators and feature covariance matrix estimators, especially in challenging situations where the learner has no knowledge about the context distribution and there is no simulator available.
The paper manages to achieve an improved bound on the bias. The techniques used surpass those used in previous studies [DLWZ23, SKM23], leading to a significant improvement in the algorithm's performance and making it more effective in practice.
The introduction of feature centralization is also a notable strength. By centralizing the features by $\hat x_t$, an estimation of the mean features under the current policy, the bias $y_t - \hat y_t$ appears in a nice form that can be compensated by a bonus term. This approach provides an elegant solution to handling bias in the estimator.
The paper successfully handles the issue of strong dependence between the policy and the empirical context distribution, Dˆt, which typically rules out canonical concentration bounds.
The paper addresses the need for high efficiency in reusing the context samples, which is a challenging problem often not adequately handled by existing methods.
Weaknesses
A notable weakness of the paper is the absence of empirical or numerical experiments to validate the theoretical results. Without practical implementation and testing of the proposed estimators on different datasets, it becomes difficult to assess their efficacy and performance.
Questions
How might these estimators handle high-dimensional data? Are there potential ways to improve their performance in such scenarios in future work?
Could the presented estimators be generalized to other types of bandit problems, such as non-linear contextual bandit problems?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed 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
The authors adequately addressed the limitations as I could tell.
==================================================
Post-Rebuttal:
I appreciate the response from the authors, and it addresses most of my concerns. Though I still believe the empirical experiments and the comparisons to other existing methods should be an important part of the work, this is still a strong theoretical paper.