論文の概要: Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms
- arxiv url: http://arxiv.org/abs/2206.08776v1
- Date: Fri, 17 Jun 2022 13:47:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-20 12:54:45.005657
- Title: Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms
- Title(参考訳): 共有可能な有限容量アームを用いたマルチプレイ確率バンディット
- Authors: Xuchuang Wang, Hong Xie, John C.S. Lui
- Abstract要約: マルチプレイマルチアームバンディット(MP-MAB)問題を共有アーム設定で一般化する。
各共有可能なアームは、有限報酬能力と'per-load'の報酬分布を有する。
本稿では,この問題に対処し,その後悔すべき上限を証明するためのオンライン学習アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 32.313813562222066
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We generalize the multiple-play multi-armed bandits (MP-MAB) problem with a
shareable arm setting, in which several plays can share the same arm.
Furthermore, each shareable arm has a finite reward capacity and a ''per-load''
reward distribution, both of which are unknown to the learner. The reward from
a shareable arm is load-dependent, which is the "per-load" reward multiplying
either the number of plays pulling the arm, or its reward capacity when the
number of plays exceeds the capacity limit. When the "per-load" reward follows
a Gaussian distribution, we prove a sample complexity lower bound of learning
the capacity from load-dependent rewards and also a regret lower bound of this
new MP-MAB problem. We devise a capacity estimator whose sample complexity
upper bound matches the lower bound in terms of reward means and capacities. We
also propose an online learning algorithm to address the problem and prove its
regret upper bound. This regret upper bound's first term is the same as regret
lower bound's, and its second and third terms also evidently correspond to
lower bound's. Extensive experiments validate our algorithm's performance and
also its gain in 5G & 4G base station selection.
- Abstract(参考訳): 複数のプレイが同じアームを共有することができる共有可能なアーム設定でマルチプレイマルチアームバンディット(mp-mab)問題を一般化する。
さらに、各共有可能なアームは、有限報酬能力と「単負荷」報酬分布を有しており、どちらも学習者には未知である。
共有可能なアームからの報酬は負荷依存であり、これは「負荷当たり」の報酬であり、アームを引っ張るプレイの数と、そのプレイ数が容量制限を超える場合の報酬能力とを乗じる。
負荷当たりの報酬」がガウス分布に従えば、負荷依存の報酬から学習能力の限界が低くなり、また、この新たなMP-MAB問題に対する後悔の少ない境界が証明される。
我々は,サンプルの複雑さが報酬手段とキャパシティの観点で下限に一致するキャパシティ推定器を考案する。
また,この問題に対処し,その後悔の上限を立証するためのオンライン学習アルゴリズムを提案する。
この後悔の上限の第1項は後悔の下限と同じであり、第2項と第3項は明らかに下限と同値である。
5Gと4Gの基地局選択では,アルゴリズムの性能および性能が向上した。
関連論文リスト
- Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。
UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
論文 参考訳(メタデータ) (2024-10-08T09:49:47Z) - Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳(メタデータ) (2024-08-20T13:57:00Z) - Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳(メタデータ) (2024-02-23T06:27:12Z) - Max-Quantile Grouped Infinite-Arm Bandits [39.7239093424124]
無限に多くの腕からなる群が多数存在するバンド問題。
本稿では,まず各グループから一定数のアームを要求し,次に有限腕グループ化された最大量子帯域幅アルゴリズムを実行する2段階アルゴリズムを提案する。
インスタンス依存と最悪のケースの後悔の両方を特徴付け、後者に一致する下位境界を提供します。
論文 参考訳(メタデータ) (2022-10-04T00:46:49Z) - Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms:
Learning Algorithms & Applications [32.313813562222066]
本研究では,分散化されたプレイヤーが協調して同じマルチアームバンディットをプレイし,総累積報酬を最大化する方法について検討する。
既存のMMABモデルは、複数のプレイヤーが同じ腕を引っ張った場合、衝突を起こし、報酬がゼロになるか、衝突が無く、独立した報酬が得られると仮定する。
衝突と非衝突設定の拡張として,共有可能な資源を持つMMABを提案する。
論文 参考訳(メタデータ) (2022-04-28T13:46:59Z) - Bandit problems with fidelity rewards [7.154621689269006]
フィデリティ・バンディット問題(英: fidelity bandits problem)とは、過去にプレイヤーがその腕に「ロヤル」したかによって、各腕の報酬がフィデリティ・報酬によって増強されるK$アームのバンディット問題の変種である。
忠誠ポイントモデルでは、余分な報酬の量は、これまで腕が演奏された回数に依存する。
サブスクリプションモデルでは、追加の報酬は腕の連続的な引き分けの数に依存する。
論文 参考訳(メタデータ) (2021-11-25T11:09:43Z) - Multi-Armed Bandits with Censored Consumption of Resources [9.803834317538747]
我々は、古典的マルチアームバンディット問題のリソース対応版を考える。
各ラウンドで、学習者はアームを選択し、リソース制限を決定する。
その後、使用済みリソースの(ランダム)量が限界以下である場合、対応する(ランダム)報酬を観測する。
論文 参考訳(メタデータ) (2020-11-02T08:27:38Z) - Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
論文 参考訳(メタデータ) (2020-02-13T08:53:43Z) - The Price of Incentivizing Exploration: A Characterization via Thompson
Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。
我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文 参考訳(メタデータ) (2020-02-03T04:58:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。