論文の概要: On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit

• arxiv url: http://arxiv.org/abs/2501.00924v2
• Date: Sat, 04 Jan 2025 02:17:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-07 13:45:22.667892
• Title: On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit
• Title（参考訳）: コンビニアル・マルチアーマッド・バンドにおけるフェアラーニングの低複雑さについて
• Authors: Xiaoyi Wu, Bo Ji, Bin Li,
• Abstract要約: Combinatorial Multi-Armed Bandit with fairness constraintsは、複数のアームがスーパーアームを形成するフレームワークである。 我々は、いわゆるピック・アンド・コンペア・アプローチに基づく、低複雑さなフェアラーニングアルゴリズムを開発した。 我々の理論的な証明は、この低複雑さ設計は、公正さと後悔したパフォーマンスをわずかに犠牲にするだけであることを示している。
• 参考スコア（独自算出の注目度）: 10.077816534032138
• License:
• Abstract: Combinatorial Multi-Armed Bandit with fairness constraints is a framework where multiple arms form a super arm and can be pulled in each round under uncertainty to maximize cumulative rewards while ensuring the minimum average reward required by each arm. The existing pessimistic-optimistic algorithm linearly combines virtual queue-lengths (tracking the fairness violations) and Upper Confidence Bound estimates as a weight for each arm and selects a super arm with the maximum total weight. The number of super arms could be exponential to the number of arms in many scenarios. In wireless networks, interference constraints can cause the number of super arms to grow exponentially with the number of arms. Evaluating all the feasible super arms to find the one with the maximum total weight can incur extremely high computational complexity in the pessimistic-optimistic algorithm. To avoid this, we develop a low-complexity fair learning algorithm based on the so-called pick-and-compare approach that involves randomly picking $M$ feasible super arms to evaluate. By setting $M$ to a constant, the number of comparison steps in the pessimistic-optimistic algorithm can be reduced to a constant, thereby significantly reducing the computational complexity. Our theoretical proof shows this low-complexity design incurs only a slight sacrifice in fairness and regret performance. Finally, we validate the theoretical result by extensive simulations.
• Abstract（参考訳）: フェアネス制約付きコンビニアル・マルチアーメッド・バンド( Combinatorial Multi-Armed Bandit)は、複数のアームがスーパーアームを形成し、各ラウンドで不確実性の下で引き抜いて累積報酬を最大化し、各アームに必要な最小平均報酬を確保できる枠組みである。 既存の悲観的最適化アルゴリズムは、仮想キュー長(フェアネス違反を追跡する)とアッパー信頼境界の推定を各アームの重みとして線形に組み合わせ、最大総重量のスーパーアームを選択する。 スーパーアームの数は、多くのシナリオでアームの数に指数関数的になる可能性がある。 無線ネットワークでは、干渉の制約により、スーパーアームの数は、アームの数とともに指数関数的に増加する。 すべての実現可能なスーパーアームを評価して、最大重量のスーパーアームを見つけることは、悲観的最適化アルゴリズムにおいて非常に高い計算複雑性を生じさせる。 これを回避するために、我々はいわゆる「ピック・アンド・コンペア」アプローチに基づく低複雑さなフェアラーニングアルゴリズムを開発し、ランダムに$M$の可能なスーパーアームを選定して評価する。 M$を定数に設定することで、悲観的最適化アルゴリズムにおける比較ステップの数を定数に減らし、計算の複雑さを大幅に減らすことができる。 我々の理論的な証明は、この低複雑さ設計は、公正さと後悔したパフォーマンスをわずかに犠牲にするだけであることを示している。 最後に,広範囲なシミュレーションにより理論的結果を検証した。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。 エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。 我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-03T15:10:08Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Best arm identification in rare events [0.43012765978447565]
  このフレームワークのキーとなる応用は、オンライン広告において、広告のクリックレートが1パーセントのごく一部であり、売上への最終的な転換率は高い利益であるが、再びクリックレートのごく一部になるかもしれない。 近年,BAI問題に対するアルゴリズムが開発され,正確なアーム選択に関する統計的保証を提供しながら,サンプルの複雑さを最小化している。 両腕の報酬過程は複合ポアソン法によりよく近似され、より高速なアルゴリズムに到達し、サンプルの複雑さはわずかに増大する。
  論文  参考訳（メタデータ） (2023-03-14T04:51:24Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。