論文の概要: No Discounted-Regret Learning in Adversarial Bandits with Delays
- arxiv url: http://arxiv.org/abs/2103.04550v1
- Date: Mon, 8 Mar 2021 05:15:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-09 15:12:38.352797
- Title: No Discounted-Regret Learning in Adversarial Bandits with Delays
- Title（参考訳）: 遅延を伴う敵対的バンディットにおけるディスカウント・リグレット学習
- Authors: Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, Jose Blanchet
- Abstract要約: アルゴリズムが「割引なし」の場合、予想される遊びの割引エルゴジック分布が粗相関平衡(CCE)の集合に収束することを示した。
ゼロサムゲームでは、Nash平衡のセットに収束する割引エルゴディック平均のプレイには、ディスカウントレグレットが十分ではないことを示します。
- 参考スコア（独自算出の注目度）: 40.670563413892154
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider a player that in each round $t$ out of $T$ rounds chooses an action
and observes the incurred cost after a delay of $d_{t}$ rounds. The cost
functions and the delay sequence are chosen by an adversary. We show that even
if the players' algorithms lose their "no regret" property due to too large
delays, the expected discounted ergodic distribution of play converges to the
set of coarse correlated equilibrium (CCE) if the algorithms have "no
discounted-regret". For a zero-sum game, we show that no discounted-regret is
sufficient for the discounted ergodic average of play to converge to the set of
Nash equilibria. We prove that the FKM algorithm with $n$ dimensions achieves a
regret of
$O\left(nT^{\frac{3}{4}}+\sqrt{n}T^{\frac{1}{3}}D^{\frac{1}{3}}\right)$ and the
EXP3 algorithm with $K$ arms achieves a regret of $O\left(\sqrt{\ln
K\left(KT+D\right)}\right)$ even when $D=\sum_{t=1}^{T}d_{t}$ and $T$ are
unknown. These bounds use a novel doubling trick that provably retains the
regret bound for when $D$ and $T$ are known. Using these bounds, we show that
EXP3 and FKM have no discounted-regret even for $d_{t}=O\left(t\log t\right)$.
Therefore, the CCE of a finite or convex unknown game can be approximated even
when only delayed bandit feedback is available via simulation.
- Abstract（参考訳）: T$ラウンドのそれぞれのラウンド$t$でアクションを選択し、$d_{t}$ラウンドの遅延後に発生したコストを観察するプレイヤーを考えてみましょう。
コスト関数と遅延シーケンスは、相手によって選択される。
プレイヤーのアルゴリズムが大きな遅延のために「後悔しない」特性を失ったとしても、期待されるプレイのエルゴード分布は、アルゴリズムが「割引-回帰しない」ならば、粗い相関均衡(CCE)の集合に収束することを示す。
ゼロサムゲームでは、Nash平衡のセットに収束する割引エルゴディック平均のプレイには、ディスカウントレグレットが十分ではないことを示します。
我々は、$n$次元のFKMアルゴリズムが$O\left(nT^{\frac{3}{4}}+\sqrt{n}T^{\frac{1}{3}}D^{\frac{1}{3}}\right)$と$K$腕のEXP3アルゴリズムが$O\left(\sqrt{\ln K\left(KT+D\right)}\right)$と$D=\sum_{t=1}^{T}d_{t}$と$T$の後悔を達成することを証明している。
これらの境界は、$D$と$T$が知られているときにバインドされた後悔を確実に保持する、新しい倍増トリックを使用します。
これらの境界を用いて、$d_{t}=O\left(t\log t\right)$ であっても EXP3 と FKM は割引レグレットを持たないことを示す。
したがって、シミュレーションにより遅延帯域フィードバックのみが利用可能であっても、有限または凸未知ゲームのCCEを近似することができる。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
論文 参考訳（メタデータ） (2024-02-14T13:08:26Z) - Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits [3.5955736977697073]
K$アームと$T$トライアルを持つシングルパス設定では、$o(K)$メモリを持つ任意のアルゴリズムに対して、後悔の少ない$Omega(T2/3)$が証明されている。
本稿では,o(K)$メモリを持つアルゴリズムに対して,Omega(K/3log/3(T))$に制限された後悔の低減を図る。
提案アルゴリズムはベンチマーク均一探索アルゴリズムを大きなマージンで一貫して上回り、時には後悔を最大70%削減することを示した。
論文 参考訳（メタデータ） (2023-06-03T22:41:44Z) - A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。
我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。
また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
論文 参考訳（メタデータ） (2022-06-29T20:49:45Z) - Better Best of Both Worlds Bounds for Bandits with Switching Costs [37.71741656687868]
本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。
本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
論文 参考訳（メタデータ） (2022-06-07T08:22:56Z) - Bounded Memory Adversarial Bandits with Composite Anonymous Delayed
Feedback [10.179145161000315]
複合匿名遅延フィードバックを用いた対向帯域幅問題について検討した。
この設定では、アクションの損失は$d$コンポーネントに分割され、アクションが選択された後に連続してラウンドが分散される。
損失シーケンスがメモリ境界である場合でも,$Omega(T)$疑似後悔が発生することを示す。
論文 参考訳（メタデータ） (2022-04-27T08:32:35Z) - Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer
Games [121.50979258049135]
我々は、すべてのプレイヤーが、時空不変の学習速度で我々のダイナミクスに従うとき、時間$T$までの時空二階パス長は、$O(log T)$で有界であることを示す。
提案する学習力学は, 直観的正規化学習と, 自己一致障壁を併用した新しい学習手法である。
論文 参考訳（メタデータ） (2022-04-25T03:20:16Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。