論文の概要: Complete Policy Regret Bounds for Tallying Bandits
- arxiv url: http://arxiv.org/abs/2204.11174v1
- Date: Sun, 24 Apr 2022 03:10:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-26 12:11:43.773489
- Title: Complete Policy Regret Bounds for Tallying Bandits
- Title（参考訳）: バンダリングのための完全な政策レグレット境界
- Authors: Dhruv Malik, Yuanzhi Li, Aarti Singh
- Abstract要約: 政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
- 参考スコア（独自算出の注目度）: 51.039677652803675
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Policy regret is a well established notion of measuring the performance of an
online learning algorithm against an adaptive adversary. We study restrictions
on the adversary that enable efficient minimization of the \emph{complete
policy regret}, which is the strongest possible version of policy regret. We
identify a gap in the current theoretical understanding of what sorts of
restrictions permit tractability in this challenging setting. To resolve this
gap, we consider a generalization of the stochastic multi armed bandit, which
we call the \emph{tallying bandit}. This is an online learning setting with an
$m$-memory bounded adversary, where the average loss for playing an action is
an unknown function of the number (or tally) of times that the action was
played in the last $m$ timesteps. For tallying bandit problems with $K$ actions
and time horizon $T$, we provide an algorithm that w.h.p achieves a complete
policy regret guarantee of $\tilde{\mathcal{O}}(mK\sqrt{T})$, where the
$\tilde{\mathcal{O}}$ notation hides only logarithmic factors. We additionally
prove an $\tilde\Omega(\sqrt{m K T})$ lower bound on the expected complete
policy regret of any tallying bandit algorithm, demonstrating the near
optimality of our method.
- Abstract（参考訳）: ポリシー後悔は、オンライン学習アルゴリズムのパフォーマンスを適応的な敵に対して測定する、確立された概念である。
我々は,政策後悔の最も強力なバージョンである 'emph{complete policy regret}' の効率的な最小化を可能にする敵に対する制限について検討する。
この困難な環境では、どのような制限がトラクタビリティを許すのか、現在の理論的理解のギャップを識別する。
このギャップを解決するため、確率的多武装バンディットの一般化を考察し、これを 'emph{tallying bandit} と呼ぶ。
これは、$m$-memory bounded adversaryを持つオンライン学習セットで、アクションをプレイする平均損失は、最後の$m$の時間ステップでアクションがプレイされた回数(または集計値)の未知の関数である。
k$ action と time horizon $t$ のバンドイット問題に対して、w.h.p は$\tilde{\mathcal{o}}(mk\sqrt{t})$ の完全なポリシー後悔保証を達成するアルゴリズムを提供し、ここで $\tilde{\mathcal{o}}$ notation は対数因子のみを隠蔽する。
さらに,計算量の多いbanditアルゴリズムの予測された完全ポリシー後悔に対する$\tilde\omega(\sqrt{m k t})$の上限を証明し,近似的最適性を示す。
関連論文リスト
- Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Weighted Tallying Bandits: Overcoming Intractability via Repeated
Exposure Optimality [46.445321251991096]
推薦システムやクラウドソーシングアプリケーションでは、人間の好みや能力はアルゴリズムの最近の行動の関数であることが多い。
我々は、この設定を一般化するWeighted Tallying Bandit (WTB)を導入し、アクションの損失が、前回の$m$のタイムステップで腕が演奏された回数のエンフ和関数であることを要求して、この設定を一般化する。
我々は、$K$アクションと水平線$T$の問題に対して、逐次除去アルゴリズムの簡単な変更は、$O left( sqrtKT + m+)を持つことを示した。
論文 参考訳（メタデータ） (2023-05-04T15:59:43Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Bounded Memory Adversarial Bandits with Composite Anonymous Delayed
Feedback [10.179145161000315]
複合匿名遅延フィードバックを用いた対向帯域幅問題について検討した。
この設定では、アクションの損失は$d$コンポーネントに分割され、アクションが選択された後に連続してラウンドが分散される。
損失シーケンスがメモリ境界である場合でも,$Omega(T)$疑似後悔が発生することを示す。
論文 参考訳（メタデータ） (2022-04-27T08:32:35Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z) - A Short Note on Soft-max and Policy Gradients in Bandits Problems [0.0]
バンディット問題に対するソフトマックス常微分方程式に対する後悔の束縛を与える短い議論を与える。
我々は、またもやバンディット問題に対して、異なるポリシー勾配アルゴリズムに対して同様の結果を得る。
論文 参考訳（メタデータ） (2020-07-20T17:30:27Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。