論文の概要: On the Regularity and Fairness of Combinatorial Multi-Armed Bandit

• arxiv url: http://arxiv.org/abs/2509.12457v1
• Date: Mon, 15 Sep 2025 21:08:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-17 17:50:52.768491
• Title: On the Regularity and Fairness of Combinatorial Multi-Armed Bandit
• Title（参考訳）: コンビニアル・マルチアーマッド・バンドの規則性と公正性について
• Authors: Xiaoyi Wu, Bin Li,
• Abstract要約: 本論文は,無線ネットワークにおける2つの重要な応用から着想を得たものである。 累積報酬を最大化するだけでなく、武器間の公平性を保証することも必要です。 これら3つの目的を達成するために,パラメータ化された正規かつ公正な学習アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 8.61754191125565
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The combinatorial multi-armed bandit model is designed to maximize cumulative rewards in the presence of uncertainty by activating a subset of arms in each round. This paper is inspired by two critical applications in wireless networks, where it's not only essential to maximize cumulative rewards but also to guarantee fairness among arms (i.e., the minimum average reward required by each arm) and ensure reward regularity (i.e., how often each arm receives the reward). In this paper, we propose a parameterized regular and fair learning algorithm to achieve these three objectives. In particular, the proposed algorithm linearly combines virtual queue-lengths (tracking the fairness violations), Time-Since-Last-Reward (TSLR) metrics, and Upper Confidence Bound (UCB) estimates in its weight measure. Here, TSLR is similar to age-of-information and measures the elapsed number of rounds since the last time an arm received a reward, capturing the reward regularity performance, and UCB estimates are utilized to balance the tradeoff between exploration and exploitation in online learning. By exploring a key relationship between virtual queue-lengths and TSLR metrics and utilizing several non-trivial Lyapunov functions, we analytically characterize zero cumulative fairness violation, reward regularity, and cumulative regret performance under our proposed algorithm. These theoretical outcomes are verified by simulations based on two real-world datasets.
• Abstract（参考訳）: 組合せ多腕バンディットモデルは、各ラウンドのアームのサブセットを活性化することにより、不確実性が存在する場合の累積報酬を最大化するように設計されている。 本論文は無線ネットワークにおける2つの重要な応用に着想を得ており、累積報酬を最大化するだけでなく、腕間の公平性(つまり各腕が要求する最小報酬)と報酬規則性(各腕が報酬を受け取る頻度)を保証することが不可欠である。 本稿では,この3つの目的を達成するためのパラメータ化正規かつ公正な学習アルゴリズムを提案する。 特に、提案アルゴリズムは、仮想キュー長(フェアネス違反の追跡)、TSLR(Time-Since-Last-Reward)メトリクス、重み測定におけるアッパー信頼境界(UCB)推定を線形に結合する。 ここでは、TSLRは情報の年齢に似ており、前回アームが報酬を受けた時から経過したラウンド数を計測し、報奨レギュラー性のパフォーマンスを捉え、オンライン学習における探索と搾取のトレードオフのバランスをとるためにUCBの推定値を利用する。 仮想キュー長とTSLRメトリクスの鍵となる関係を探索し、いくつかの非自明なリアプノフ関数を利用することにより、提案アルゴリズムによる累積公正性違反、報酬規則性、累積後悔性能を解析的に特徴付ける。 これらの理論的結果は、2つの実世界のデータセットに基づくシミュレーションによって検証される。

関連論文リスト

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [60.414548453838506]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Semi-Parametric Batched Global Multi-Armed Bandits with Covariates [0.48342038441006807]
  マルチアームバンディット(MAB)フレームワークは、シーケンシャルな意思決定に広く使われているアプローチである。 本稿では,コパラメトリックと腕間の共有パラメータを持つバッチバンドの半パラメトリックフレームワークを提案する。 Batched Single-Index Dynamic binning and Successive arm elimination (BIDS) というアルゴリズムでは、バッチ化された逐次アームの除去戦略を採用している。
  論文  参考訳（メタデータ） (2025-03-01T17:23:55Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• LoRA-Ensemble: Efficient Uncertainty Modelling for Self-Attention Networks [52.46420522934253]
  本稿では,自己注意ネットワークのためのパラメータ効率のよいアンサンブル手法であるLoRA-Ensembleを紹介する。 この方法は、BatchEnsembleのような最先端の暗黙のテクニックを上回るだけでなく、Explicit Ensembleの正確さにマッチするか超える。
  論文  参考訳（メタデータ） (2024-05-23T11:10:32Z)
• Meta-Learning Adversarial Bandits [49.094361442409785]
  本研究の目的は,複数のタスクにまたがる帯域幅フィードバックを用いてオンライン学習を学習し,タスク間の平均性能を改善することである。 敵対的設定を最初に対象とするメタアルゴリズムとして,マルチアーム・バンディット(MAB)とバンディット・最適化(BLO)の2つの重要なケースに対して,特定の保証を設定するメタアルゴリズムを設計する。 我々の保証は、非正規化されたフォローザリーダーと乗法重みを組み合わせることで、オンラインで非滑らかで非Bシーケンスを学ぶのに十分であることを示すことに依存しています。
  論文  参考訳（メタデータ） (2022-05-27T17:40:32Z)
• Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Bandits [4.760079434948198]
  このようなパラメトリック情報を利用する特殊なアルゴリズムは、パラメータが誤って特定された場合、不整合学習性能が高いことを示す。 主な貢献は, (i) 固定予算純探索条件下で統計的に堅牢なMABアルゴリズムの基本的な性能限界を確立すること, (ii) 二つの近似アルゴリズムのクラスを提案することである。
  論文  参考訳（メタデータ） (2020-08-28T13:43:12Z)

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

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