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

• arxiv url: http://arxiv.org/abs/2501.00924v3
• Date: Fri, 10 Jan 2025 22:25:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:23:14.768627
• 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$を定数に設定することで、悲観的最適化アルゴリズムにおける比較ステップの数を定数に減らし、計算の複雑さを大幅に減らすことができる。 我々の理論的な証明は、この低複雑さ設計は、公正さと後悔したパフォーマンスをわずかに犠牲にするだけであることを示している。 最後に,広範囲なシミュレーションにより理論的結果を検証した。

関連論文リスト

• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  本研究では, 固定信頼度ベストアーム識別問題について検討する。 我々は任意の境界の停止時間で2つ下げる。 腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T09:05:11Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$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)
• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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)

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

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