Meta-Learning Adversarial Bandit Algorithms

Summary

This paper considers learning several adversarial tasks with different loss functions simultaneously, hoping to attain better task-averaged regret if the tasks are "similar" enough (e.g., the optimal actions of all tasks concentrate on a small subset). A general meta-learning framework is derived by deploying three different algorithms as meta-learners to optimize the hyper-parameters of the base learners (OMD). It then applies to MABs and BLOs, providing various high-probability or expected regret bounds.

Strengths

1. The studied problem is well-motivated. According to the authors, while the stochastic variant of this meta-learning problem is well-studied, the adversarial version tackled by this paper has never been solved. 2. The algorithmic idea is well-illustrated and thus the framework is easy to understand. 3. The framework is applied to various base-learners to prove its effectiveness, including MABs with implicit exploration or guaranteed exploration and BLOs with self-concordant barriers.

Weaknesses

1. The design of the meta-learner does not look pretty exciting. Given the expression of $U_t$ in Eq. (3), it appears unsurprising that the adopted optimizers (FTL, EWOO, and MW) can be applied to their respective objectives. In other words, it seems that the technical contribution of this paper is not solid enough -- the analyses of meta-learners and base-learners are both not novel. However, I do feel the overall result is interesting. 2. I am unsure whether the task similarity measure can generalize over the "support" of the optimizers. Consider a special case where most of the tasks share the same optimizer but there are a few (say $\sqrt T$) outliers, would the bound scale with $\sqrt[4]{T}$ or $\mathcal O(1)$? In this case, if a meta-learner successfully rules out those outliers, the bound should scale by $\mathcal O(1)$; but using the sparsity $s$ would only give $\sqrt[4]{T}$. Intuitively, as $H_\beta$ is taken to the average of all $\hat x$'s, such a distribution will be very different from a uniform distribution (i.e., there are $\sqrt T$ optimizers each associated with $\sqrt T$ tasks); though I'm not sure whether the current framework can capture this. 3. (minor) The bounds in the main text contain so many terms that it is hard to interpolate. Informal expressions (like Eq. (13) or Eq. (19)) can be shortened using $o_T(1)$ to highlight the main terms.

Questions

See Weakness 1 & 2.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Clearly stated

Summary

This paper focused on online meta-learning with bandit feedback, and developed and applied a meta-algorithm for learning to initialize and tune bandit algorithms, obtaining task-average regret guarantees for both MAB and linear bandits. Specifically, a meta-algorithm was developed for learning the variants of OMD, which was further applied to OMD with the Tsallis regularizer. Furthermore, the meta-algorithm was adapted to the adversarial BLO problem via setting the regularizer to be a self-concordant barrier function.

Strengths

- This paper is the first to consider meta-learning under adversarial bandit feedback. - A meta-algorithm was designed for learning the variants of OMD, which can simultaneously tune the initialization and other hyperparameters. - Strong theoretical performance guarantees were presented for the proposed algorithm. - The paper is well-written and easy to follow though it is heavy in theory.

Weaknesses

- This paper mainly focused on the pure adversarial settings. As the authors mentioned, there are extensive works studied the stochastic settings, and given the popularity of "best-of-both-worlds" settings in the community, can you envision what is the major challenges to generalize the solutions to the best-of-both-worlds settings, from both the algorithmic and performance analysis perspectives? - As the paper considered the applications of the proposed algorithms, it may be interesting to do some case studies with real-world applications, rather than only on theoretical applications.

Questions

- This paper mainly focused on the pure adversarial settings. As the authors mentioned, there are extensive works studied the stochastic settings, and given the popularity of "best-of-both-worlds" settings in the community, can you envision what is the major challenges to generalize the solutions to the best-of-both-worlds settings, from both the algorithmic and performance analysis perspectives?

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

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

n/a societal impact.

Summary

In this paper, the authors consider an online meta-learning problem with the adversarial online-with-online partial information setting, where a learner selects parameters across T tasks with m rounds and can utilize similarity between tasks to achieve a low regret. First, the authors propose a meta algorithm which optimizes hyperparameters of the inner loop algorithm (OMD). As an instance of this algorithm, the authors consider OMD for MAB and BLO (bandit linear optimization). Then, they prove several upper bounds of the average regret across $T$ tasks using a similarity of optimal parameters across tasks.

Strengths

1. While existing papers considered online-with-online meta-learning in stochastic or full-information setting, this paper considers the adversarial bandit feedback setting, which is practically important. 2. Although the proposed algorithm is based on one in the full information setting, there is novelty due to the bandit feed back (e.g., estimation of true $H_\beta$). 3. The authors provide regret upper bounds under several settings and results seems valid.

Weaknesses

1. There is no discussion on lower bounds. Therefore, it is not clear whether the proposed method is optimal.

Questions

1. In the related work section, the authors compare their algorithm to algorithm for dynamic regret optimization, but they discuss only the number of switches. There are algorithms whose regret bounds involve total variance of the environment (e.g. $\Delta$ in Wei, Chen-Yu, and Haipeng Luo. "Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach." Conference on learning theory, 2021.). Are these algorithms related to the problem setting in Sec 3.2? Is it possible to provide a comparison? 2. In the stochastic setting, is there a known lower bound?

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.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

The paper proposes an online mirror descent approach for adversarial bandit feedback-based online meta learning, utilizing FTL for initialization, EWOO for step-size, and MW for regularizer-specific parameters. The proposed method is applied to two widely adopted applications: multi-armed bandits (MAB) with Tsallis regularizer and bandit linear optimization (BLO) with self-concordant barrier function regularizer. The authors provide theoretical analysis on asymptotic task-averaged regret for MAB and BLO.

Strengths

The paper is well-written and seems to cover an important topic in the community. I check some proofs, and they seems correct.

Weaknesses

While the paper is theoretical in nature, it would be beneficial to include some empirical results to further validate the proposed approach.

Questions

The reviewer is not very familiar with this topic and would like to see the comments and feedback from other reviewers before asking further questions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

It would be nice to provide empirical results ( it is not mandatory and the paper's contribution is still valuable without them).

Summary

The paper discusses online meta-learning with bandit feedback to enhance performance across multiple tasks that share a natural similarity measure. The study focuses on the adversarial online-within-online partial-information setting and proposes meta-algorithms that combine outer learners to optimize the initialization and other hyperparameters of an inner learner for two cases: multi-armed bandits (MAB) and bandit linear optimization (BLO). For MAB, the meta-learners use the Tsallis-entropy generalization of Exp3, and the task-averaged regret improves when the entropy of the optima-in-hindsight is small. For BLO, the approach involves learning to initialize and tune online mirror descent (OMD) with self-concordant barrier regularizers, where the task-averaged regret is related to an action space-dependent measure induced by these regularizers. The guarantees provided in the study are based on demonstrating that unregularized follow-the-leader combined with two levels of low-dimensional hyperparameter tuning can effectively learn a sequence of affine functions of non-Lipschitz and sometimes non-convex Bregman divergences, which bound the regret of OMD.

Strengths

This paper designs a meta-algorithm combining FTL, EWOO, MW to set the initialization, step-size, and the regularizer. Then, it has to direct applications for MAB and BLO. Then, the authors provide rigorous average regret analysis with Tsallis entropy, which are the first results for online learning with Bregman divergences.

Weaknesses

It will be better if authors can provide some real-world applications that the designed algorithm can adapt to.

Questions

(1) For the MAB algorithms, there may be only one served task in each round, i.e., observe the loss. In this case, how to run algorithm 1 and do we need to update the parameters of all tasks?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

.

Summary

This paper introduces a meta-learning algorithmic framework for adversarial bandits, designed to fine-tune the initialization and hyperparameters of the internal learner, thereby enhancing performance across multiple tasks. The efficacy of this approach is validated via a theoretical analysis on multi-armed bandits and linear bandits. The authors also propose a task-similarity measure with significant implications concerning entropy and proximity to the task boundary.

Strengths

- The paper addresses meta-learning under adversarial bandit feedback, which is an interesting problem by itself, and the meta-learning approach poses a solid contribution to the bandit community, with a new notion of task-similarity based on entropy. - The concrete steps towards building the algorithms is clear and statements in the paper seems solid.

Weaknesses

- The paper does not have any numerical validations of the proposed algorithm. This puts doubts on the practicality of the proposed framework and methods. Synthetic as well as real-world examples should be tested upon, and comparisons against meta learning stochastic bandits should be discussed in the numerical experiments as well. - The computational complexity is not adequately addressed within the main body of the paper. Specifically, the computational overhead associated with the Multiplicative Weights (MW) method could be prohibitively high with a large grid and action space. - The interpretation of task-similarity lacks a sufficient explanation of its underlying motivation. Even in application cases where the authors justify the task-similarity measure via average entropy or proximity to the decision boundary, it remains unclear why this measure was chosen and how it compares to other task-similarity measures in stochastic bandit scenarios (and/or those with contamination or parameter noise). As it stands, the presentation in the paper makes it seem more like an artifact of the regret proof.

Questions

- Could the authors elaborate on the connections to meta-learning in adversarial Reinforcement Learning (RL)? While meta-learning for adversarial bandits appears to be a novel concept, meta-learning in adversarial RL, a generalization of bandits, has been explored in the literature, as evidenced by [1] for example. - Could the authors provide insights on how the algorithm's implementation could be optimized for efficiency? - Could the authors demonstrate the effectiveness of the model and the algorithm in a well-motivated real-world setting through numerical experiments? - Could the authors offer a more intuitive explanation of the task-similarity measure and how it compares to existing methods, beyond comments about being 'distributional assumption-free'? [1] Lin, Zichuan, Garrett Thomas, Guangwen Yang, and Tengyu Ma. "Model-based adversarial meta-reinforcement learning." Advances in Neural Information Processing Systems 33 (2020): 10161-10173.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors have acknowledged the limitations of their work, including the absence of a gap-free task similarity criterion, the assumption of known task boundaries, and the lack of a 'best-of-both-worlds' guarantee.