論文の概要: Adversarial Bandits with Multi-User Delayed Feedback: Theory and
Application
- arxiv url: http://arxiv.org/abs/2310.11188v2
- Date: Sun, 26 Nov 2023 17:18:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-30 13:53:49.228214
- Title: Adversarial Bandits with Multi-User Delayed Feedback: Theory and
Application
- Title（参考訳）: 多ユーザ遅延フィードバックを持つ逆帯域:理論と応用
- Authors: Yandi Li, Jianxiong Guo, Yupeng Li, Tian Wang, Weijia Jia
- Abstract要約: 我々は,マルチユーザ遅延フィードバックを用いた逆MAB問題を定式化し,修正されたEXP3アルゴリズム MUD-EXP3 を設計する。
本稿では,複数のユーザからの遅延フィードバック結果について考察し,内部分布に制限を加えることなく検討する。
- 参考スコア（独自算出の注目度）: 17.64363983613468
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The multi-armed bandit (MAB) models have attracted significant research
attention due to their applicability and effectiveness in various real-world
scenarios such as resource allocation, online advertising, and dynamic pricing.
As an important branch, the adversarial MAB problems with delayed feedback have
been proposed and studied by many researchers recently where a conceptual
adversary strategically selects the reward distributions associated with each
arm to challenge the learning algorithm and the agent experiences a delay
between taking an action and receiving the corresponding reward feedback.
However, the existing models restrict the feedback to be generated from only
one user, which makes models inapplicable to the prevailing scenarios of
multiple users (e.g. ad recommendation for a group of users). In this paper, we
consider that the delayed feedback results are from multiple users and are
unrestricted on internal distribution. In contrast, the feedback delay is
arbitrary and unknown to the player in advance. Also, for different users in a
round, the delays in feedback have no assumption of latent correlation. Thus,
we formulate an adversarial MAB problem with multi-user delayed feedback and
design a modified EXP3 algorithm MUD-EXP3, which makes a decision at each round
by considering the importance-weighted estimator of the received feedback from
different users. On the premise of known terminal round index $T$, the number
of users $M$, the number of arms $N$, and upper bound of delay $d_{max}$, we
prove a regret of $\mathcal{O}(\sqrt{TM^2\ln{N}(N\mathrm{e}+4d_{max})})$.
Furthermore, for the more common case of unknown $T$, an adaptive algorithm
AMUD-EXP3 is proposed with a sublinear regret with respect to $T$. Finally,
extensive experiments are conducted to indicate the correctness and
effectiveness of our algorithms.
- Abstract（参考訳）: マルチアームバンディット(MAB)モデルは、リソース割り当て、オンライン広告、動的価格設定など、様々な現実のシナリオに適用可能性や有効性から、研究の注目を集めている。
重要な分野として,学習アルゴリズムに挑戦するために,概念敵が各アームに関連する報酬分布を戦略的に選択し,エージェントがアクションを取ると対応する報酬フィードバックを受け取るまでの遅延を経験する,多くの研究者によって,遅延フィードバックを伴う敵対的mab問題が提案され,研究されている。
しかし、既存のモデルは1人のユーザーのみが生成するフィードバックを制限するため、複数のユーザーの一般的なシナリオ(例えば、一群のユーザーに対する広告推薦)にモデルは適用できない。
本稿では,複数ユーザからのフィードバックが遅延し,内部分布が制限されないことを考察する。
対照的に、フィードバック遅延は任意であり、予めプレイヤーに未知である。
また、ラウンド内の異なるユーザにとって、フィードバックの遅延は遅延相関の仮定を持たない。
そこで,マルチユーザによる遅延フィードバックを用いた逆MAB問題を定式化し,異なるユーザからのフィードバックの重み付けを考慮し,各ラウンドで決定を行うEXP3アルゴリズムを改良したMUD-EXP3を設計する。
既知の端末ラウンドインデックス$T$, ユーザ数$M$, アーム数$N$, 遅延上限$d_{max}$の前提で、$\mathcal{O}(\sqrt{TM^2\ln{N}(N\mathrm{e}+4d_{max})} の後悔を証明する。
さらに、未知の$T$のより一般的な場合、適応アルゴリズム AMUD-EXP3 は$T$に対するサブ線形後悔と共に提案される。
最後に,アルゴリズムの正しさと有効性を示すため,広範な実験を行った。
関連論文リスト
- Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays [25.757803459592104]
本研究では,有益性制約下での非制限フィードバック遅延を用いた半帯域問題について検討する。
これはクラウドソーシングやオンライン広告などのアプリケーションによって動機付けられており、即時フィードバックはすぐには利用できない。
我々は,その利点に基づいて,制限のないフィードバック遅延の下で腕を選択するための新しいバンディットアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-22T07:36:27Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays [24.998122268199797]
本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。
我々のアルゴリズムは任意の過剰な遅延を許容し、$T$をオーダーすることができる。
論文 参考訳（メタデータ） (2023-08-21T12:17:40Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳（メタデータ） (2023-05-25T14:02:12Z) - Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit
Feedback [39.12903814606534]
本稿では,過度な(期待している)報酬と全帯域遅延フィードバックを伴うマルチアームバンドの問題について検討する。
遅延したフィードバックは過去のアクションからの報酬のコンポーネントで構成されており、サブコンポーネント間で未知の分割がある。
提案アルゴリズムは,合成匿名フィードバックの遅延により,他の全帯域アプローチより優れていることを示す。
論文 参考訳（メタデータ） (2023-03-23T18:38:33Z) - Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When
Partial Feedback Counts [53.579515853222986]
時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。
この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。
本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:56:59Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳（メタデータ） (2022-03-18T08:03:20Z) - Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback [67.63049551992816]
エピソードマルコフ決定過程(MDP)におけるオンライン学習について検討した。
ほぼ最適の$sqrtK + D$ regret, where $K$ is the number of episodes, $D = sum_k=1K dk$ is the total delay。
論文 参考訳（メタデータ） (2022-01-31T12:34:26Z) - Combinatorial Multi-armed Bandits for Resource Allocation [23.869080705146395]
モチベーションの例としては、限られたコンピューティング時間や無線スペクトル帯域を複数のユーザに割り当てることが挙げられる。
意思決定者は、各ユーザの報酬に対するフィードバックから、各ユーザに割り当てられたリソースの価値を学習すべきである。
論文 参考訳（メタデータ） (2021-05-10T13:55:30Z) - Partial Bandit and Semi-Bandit: Making the Most Out of Scarce Users'
Feedback [62.997667081978825]
本稿では,ユーザのフィードバックを考慮し,3つの戦略を用いて評価する手法を提案する。
ユーザからのフィードバックが制限されているにも関わらず(全体の20%以下)、我々の手法は最先端のアプローチと同じような結果が得られる。
論文 参考訳（メタデータ） (2020-09-16T07:32:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。