論文の概要: A Modified EXP3 and Its Adaptive Variant in Adversarial Bandits with
Multi-User Delayed Feedback
- arxiv url: http://arxiv.org/abs/2310.11188v1
- Date: Tue, 17 Oct 2023 12:08:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 16:10:58.578642
- Title: A Modified EXP3 and Its Adaptive Variant in Adversarial Bandits with
Multi-User Delayed Feedback
- Title（参考訳）: マルチユーザ遅延フィードバックを用いた逆帯域修正EXP3とその適応変数
- Authors: Yandi Li, Jianxiong Guo
- Abstract要約: マルチユーザ遅延フィードバックを用いた対向型マルチアームバンディット問題を定式化する。
ラウンド内の異なるユーザにとって、フィードバックの遅延には遅延相関がない。
未知の$T$の場合、AMUD-EXP3という適応アルゴリズムが提案される。
- 参考スコア（独自算出の注目度）: 0.49109372384514843
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For the adversarial multi-armed bandit problem with delayed feedback, we
consider that the delayed feedback results are from multiple users and are
unrestricted on internal distribution. As the player picks an arm, feedback
from multiple users may not be received instantly yet after an arbitrary delay
of time which is unknown to the player in advance. For different users in a
round, the delays in feedback have no latent correlation. Thus, we formulate an
adversarial multi-armed bandit problem with multi-user delayed feedback and
design a modified EXP3 algorithm named 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 named 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（参考訳）: 遅延フィードバックを伴う敵対的マルチアームドバンディット問題に対して,遅延フィードバックの結果は複数のユーザによるものであり,内部分布に制限がないと考える。
プレイヤーが腕を選ぶと、事前にプレイヤーに不明な任意の遅延時間後、複数のユーザーからのフィードバックがすぐに受信されない場合がある。
ラウンド内の異なるユーザにとって、フィードバックの遅延には遅延相関がない。
そこで本研究では,マルチユーザ遅延フィードバックによる対向型多腕バンディット問題を定式化し,異なるユーザから受信したフィードバックの重み付け推定値を考慮して各ラウンドにおいて決定を行うmud-exp3と呼ばれる修正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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。