Multi-Task Best Arm Identification with Risk Constraint
Multi-Task，Best Arm Identification，Risk Constraint， Fixed Confidence
Yes
No ethics review needed.
see Weaknesses.
1. The methodology employed is robust, featuring a detailed analysis across several variants: the foundational algorithm is presented in Section 4.1, an optimized version in Section 4.2, and an adaptation to linear settings discussed in Section 5.

2. The numerical experiments conducted are thorough, employing ESR, ASR, and FWSR as benchmark algorithms.
This paper tackles the complex problem of Best Arm Identification in sequential decision-making, focusing on multi-task scenarios with risk constraints. The authors derive a tight lower bound on sample complexity and propose a Track-and-Stop strategy with optimal performance. Their approach balances tasks and constraints effectively, and results demonstrate strong performance in numerical experiments, extending findings to the linear bandit setting.
The technical innovation presented in this paper appears to be limited. Algorithm 1 essentially replicates the Track-and-stop method referenced in [1]. Consequently, the paper's novelty should primarily be evaluated based on the efficient sampling rule introduced in Section 4.2. Nevertheless, this sampling rule closely resembles the BestChallenger method detailed in [1, Section 6], and Equation (17) directly corresponds to the definition of BestChallenger within this setting. Furthermore, the authors should have cited the BestChallenger method in Section 4.2 to acknowledge the previous researchers' efforts.

[1] Garivier, A., & Kaufmann, E. (2016, June). Optimal best arm identification with fixed confidence. In Conference on Learning Theory (pp. 998-1027). PMLR.
Yes
No ethics review needed.
Please see the weaknesses above.
1.	The authors propose a multi-task BAI problem with risk constraint applicable to various real-world problems. The authors establish a tight, instance-dependent lower bound on the sample complexity required to guarantee a high probability identification of the feasible and optimal arm for each task.
2.	Based on the lower bound, the authors derive the optimality conditions for the static optimal sampling ratio, and discuss how this ratio balances the difficulty across different tasks and constraints, illustrating the trade-off between optimality and feasibility. In addition, the authors present a closed-form formula for the problem’s hardness by analyzing some challenging instances.
3.	The authors develop a Track-and-Stop strategy for the multi-task BAI problem with risk constraint, achieving asymptotically optimal sample complexity and a computationally efficient strategy that iteratively solves the optimality conditions. What’s more, the authors also extend their sample complexity results to the linear bandit setting. Numerical experiments show that the proposed algorithm performs well in comparison to several benchmarks.
4.	This paper is overall well-written and clearly organized.
This paper introduces a multi-task best arm identification problem with risk constraint in the fixed-confidence setting, where each arm has multiple performance metrics. The agent aims to optimize one metric, while ensuring that the quantiles of other metrics remain below specified thresholds for each task. The authors first build a tight, instance-dependent lower bound on sample complexity. Based on this bound, the authors establish optimality conditions for the static optimal sampling ratio, and illustrate how it balances among different tasks and constraints, while addressing the tradeoff between optimality and feasibility. In addition, the authors design a Track-and-Stop strategy with asymptotically optimal sample complexity, and a computationally efficient strategy that iteratively solves the optimality conditions. Finally, the authors extend their results to the linear bandit setting. Numerical experiments show that the proposed algorithm performs relatively well.
1.	The motivation of the proposed problem formulation is not very clear. Can the authors describe 1-2 concrete application scenarios for the proposed problem formulation, in particular, connect the risk constraint formulation with real-world requirements on risk management.
2.	It is a little surprising that the sample complexity of Algorithm 1 (Theorem 3) perfectly matches the lower bound for the multi-task best arm identification problem with risk constraints, even for logarithmic factors. Can the authors give the intuition on why Algorithm 1 can avoid a union bound over the number of arms and tasks in the logarithmic factor?
3.	The formulas and notations in this paper are dense. The authors should add more intuition behind the algorithm design and theoretical results.
Yes
No ethics review needed.
1. Is there any specific reason that the best arm identification problem of all tasks need to be considered and solved all-together?
2. Is it possible to derive performance guarantees (asymptotic or finite-time) for the SEQSR algorithm which can be quantitatively compared with H^* or H in proposition 1?
3. The formulation that the agent needs to choose a metric at each time-step and only observes the reward of this metric lacks motivation. Even though this formulation is statistically harder, it also produces enough variables \omega in Theorem 1, so that one could convert the lower bound to the optimality condition in Theorem 2. The reviewer is curious on whether the algorithm development and analysis framework will still work for the setting where the reward of all metrics can be observed once an arm is pulled, i.e., Theorem 5. Is the algorithm development framework in the main body still applicable to Theorem 5? is it possible to derive the optimality condition for Theorem 5 analogous to Theorem 2?

Typo: line 409 ESR -> USR (seems this is correct according to the figure)
This paper formulates the multi-task multi-metric best arm identification problem which models a wide range of applications. The study of quantile constraints as risk measure is of novelty in the best arm identification literature which generalizes the traditional constrained bandit problems which focus purely on expectation. The theoretical lower bound and a track-and-stop based matching algorithm are provided with provable guarantees. The paper also provides some insights towards instance-dependent hardness of the problem through analysis of the lower bound and the sample complexity. Lemma 1, Lemma2, and Proposition 1 provides some understanding on how the sub-optimality gaps and variances affect the problem hardness, and how the sample complexity scales with the number of tasks, arms, and metrics. Computationally efficient algorithms are also proposed in the paper which shows good performance in simulation results.
This paper studies the problem of best arm identification with fixed confidence in a multi-task multi-objective constrained optimization setting. For each task and an arm, there are multiple metrics to consider with one primary metric that needs to be optimized while satisfying the quantile constraint for other metrics. At each time, the agent can choose a (task, metric, arm) tuple to sample, and receives the reward feedback of this specific chosen tuple, and no feedback from other metrics can be observed. The goal is to find for each task the best arm a^* which maximizes the primary metric while satisfying the constraint for all other metrics. The paper first provide and study a lower bound on the sample complexity from which the oracle static sampling strategy can be computed which requires the knowledge of the ground-truth reward of all arms, tasks and metrics. Then, the paper uses the same idea as [1] to convert the lower bound into a track-and-stop algorithm with asymptotic optimality guarantee. Computationally efficient algorithm and extension to linear bandits are also studied.

[1] Garivier, Aurélien, and Emilie Kaufmann. "Optimal best arm identification with fixed confidence." Conference on Learning Theory. PMLR, 2016.
1. Presentation: The main body presentation of this paper is somewhat not satisfactory due to 1) the studied problem is unnecessarily complicated (also see 2. Formulation) which has too many variables and quantities, and 2) the notation system is not well established and the abuse of notation is quite frequent without declaration in the main body. The notations and equations in the main body are much too involved for general readers and the authors should reconsider to simplify the paper presentation structure and avoid unnecessary notations in the main body.

2. Formulation: The multi-task problem seems unnecessarily complicated. Even though the authors does not make very clear whether there is correlation between tasks and metrics in section 2, it seems in the paper's formulation, each task is independent of one another (even in the linear bandit formulation), and therefore the agent can solve the best arm identification problem of each task independently with certain confidence \delta' one-by-one, and combine the tasks together in the end with the help of independence among tasks. It also seems in the lower bound Theorem. 1, the inverse of complexity constant H^* is defined by equalizing the complexity of each task a, which essentially equalizes the probability of error for each individual task in asymptotic regime, which makes calculating the probability of error for each individual task possible.

3. Algorithm and Analysis: The paper follows a standard track-and-stop algorithm development and analysis machinery and naturally inherits the downside of track-and-stop type algorithms [1], i.e., the proposed Algorithm 1 needs to exactly solve a min-max problem at each step, which is computationally heavy and cannot be used in practice, and the provable guarantee Theorem 3 only holds for asymptotic regimes where \delta -> 0 which does not imply finite-time guarantees (which is also why ESR is worse than SEQSR in simulation). Based on the vast amount of track-and-stop literature in various bandits[1][2][3][4] and RL problems[5][6], the proposed algorithm and performance guarantees are somewhat expected. Even though computationally effecient algorithm is provided, it does not have provable sample complexity guarantee even in simplified models.

[1] Garivier, Aurélien, and Emilie Kaufmann. "Optimal best arm identification with fixed confidence." Conference on Learning Theory. PMLR, 2016.

[2] Jedra, Yassir, and Alexandre Proutiere. "Optimal best-arm identification in linear bandits." Advances in Neural Information Processing Systems 33 (2020): 10007-10017.

[3] Barrier, Antoine, Aurélien Garivier, and Tomáš Kocák. "A non-asymptotic approach to best-arm identification for gaussian bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

[4] Russac, Yoan, et al. "A/B/n Testing with Control in the Presence of Subpopulations." Advances in Neural Information Processing Systems 34 (2021): 25100-25110.

[5] Al Marjani, Aymen, and Alexandre Proutiere. "Adaptive sampling for best policy identification in markov decision processes." International Conference on Machine Learning. PMLR, 2021.

[6] Taupin, Jerome, Yassir Jedra, and Alexandre Proutiere. "Best policy identification in linear mdps." 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2023.
Yes
No ethics review needed.
1.  How do you envision incorporating additional constraints, such as fairness, into your model? Are there specific challenges you anticipate?

2. Can you provide insights into the robustness of your results under varying conditions, such as experiments with different configurations?
1. The introduction of a multi-task BAI problem with risk constraints is a significant contribution to the literature. The problem is well-motivated with real-world applications.

2. The derivation of tight, instance-dependent lower bounds on sample complexity and optimality conditions provides a solid theoretical foundation for the proposed approach.

3. The experiments validate the algorithm's performance, showcasing its effectiveness compared to existing benchmarks.
This paper presents a novel approach to the multi-task best arm identification (BAI) problem with risk constraints in a fixed-confidence setting. The authors derive a lower bound on sample complexity, establish optimality conditions for sampling ratios, and extend the Track-and-Stop strategy. They provide numerical experiments demonstrating the performance of their proposed algorithm.
Here’s a concise and clear way to present both points in your feedback:

(1) While the paper claims to address a multi-task best arm identification (BAI) problem with risk constraints by extending the work of Garivier & Kaufmann (2016), the contributions seem to overlap with existing works in BAI with safety constraints, such as the study by Wang et al. (2022). It would be beneficial for the authors to more explicitly differentiate their approach from previous studies, providing a clearer rationale for the novelty of their contributions.

(2) There are missing periods at the end of formulas, such as in equations (8), (9), and (16). Please ensure all equations are properly punctuated for consistency and clarity.


Reference: 

[1]Wang, Z., Wagenmaker, A. J., & Jamieson, K. (2022, May). Best arm identification with safety constraints. In International Conference on Artificial Intelligence and Statistics (pp. 9114-9146). PMLR.

[2]Kaufmann, E., Cappé, O., & Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1), 1-42.
This paper tackles multi-task best arm identification with risk constraints, deriving instance-dependent sample complexity bounds and proposing an optimal algorithm, with extensions to linear bandits.
@inproceedings{
anonymous2024multitask,
title={Multi-Task Best Arm Identification with Risk Constraint},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=eq8jOD0tgl},
note={under review}
}
Best Arm Identification is a very challenging problem in sequential decision-making with many real-world applications. Existing works typically assume that all arms are feasible or/and deal with expectation-based constraints with strong assumptions, loose sample complexity bounds, and non-optimal algorithms. This paper introduces a multi-task best arm identification problem with risk constraint in the fixed-confidence setting, where each arm has multiple performance metrics. The agent aims to optimize one metric while ensuring that the quantiles of other metrics remain below specified thresholds for each task. We first derive a tight, instance-dependent lower bound on sample complexity. Based on this bound, we establish optimality conditions for the static optimal sampling ratio and illustrate how it balances among different tasks and constraints, while addressing the trade-off between optimality and feasibility. We derive a Track-and-Stop strategy with asymptotically optimal sample complexity and a computationally efficient strategy that iteratively solves the optimality conditions.  Finally, we extend our results to the linear bandit setting. Numerical experiments show that our algorithm performs relatively well.
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.
Multi-Task，Best Arm Identification，Risk Constraint， Fixed Confidence
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/66afbfe7f81ff7d9c12ded5a6b5859cc8679bb82.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.
Multi-Task Best Arm Identification with Risk Constraint
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission