論文の概要: Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Model

• arxiv url: http://arxiv.org/abs/2207.05437v1
• Date: Tue, 12 Jul 2022 10:00:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-13 22:48:03.319790
• Title: Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Model
• Title（参考訳）: 位置ベースモデルによる確率帯域と逆帯域の同時学習
• Authors: Cheng Chen, Canzhe Zhao, Shuai Li
• Abstract要約: 本研究は, 位置ベースモデルに基づくオンライン学習における課題のランク付けに関する研究である。 提案アルゴリズムは,対向環境において$O(logT)$後悔を同時に達成し,対向環境において$O(msqrtnT)$後悔を同時に達成する。 実験により,本アルゴリズムは,既存手法と競合する環境下で同時に学習できることが確認された。
• 参考スコア（独自算出の注目度）: 9.945948163150874
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online learning to rank (OLTR) interactively learns to choose lists of items from a large collection based on certain click models that describe users' click behaviors. Most recent works for this problem focus on the stochastic environment where the item attractiveness is assumed to be invariant during the learning process. In many real-world scenarios, however, the environment could be dynamic or even arbitrarily changing. This work studies the OLTR problem in both stochastic and adversarial environments under the position-based model (PBM). We propose a method based on the follow-the-regularized-leader (FTRL) framework with Tsallis entropy and develop a new self-bounding constraint especially designed for PBM. We prove the proposed algorithm simultaneously achieves $O(\log{T})$ regret in the stochastic environment and $O(m\sqrt{nT})$ regret in the adversarial environment, where $T$ is the number of rounds, $n$ is the number of items and $m$ is the number of positions. We also provide a lower bound of order $\Omega(m\sqrt{nT})$ for adversarial PBM, which matches our upper bound and improves over the state-of-the-art lower bound. The experiments show that our algorithm could simultaneously learn in both stochastic and adversarial environments and is competitive compared to existing methods that are designed for a single environment.
• Abstract（参考訳）: オンラインラーニング・トゥ・ランク(oltr)は、ユーザーのクリック行動を記述する特定のクリックモデルに基づいて、大きなコレクションからアイテムのリストを選択することをインタラクティブに学習する。 この問題に対する最近の研究は、学習過程においてアイテムの魅力が不変であると仮定される確率的環境に焦点を当てている。 しかし、多くの現実世界のシナリオでは、環境は動的あるいは任意に変化する可能性がある。 本研究は,位置ベースモデル(PBM)の下での確率的・対角的環境におけるOLTR問題を研究する。 本稿では,Tsallisエントロピーを用いたフォロー・ザ・レギュラライズド・リーダー(FTRL)フレームワークに基づく手法を提案する。 提案アルゴリズムは,確率的環境では$o(\log{t})$ regretと,敵対的環境では$o(m\sqrt{nt})$ regretを同時に達成できることを証明し,$t$はラウンド数,$n$はアイテム数,$m$は位置数である。 また、逆数 PBM の次数 $\Omega(m\sqrt{nT})$ の下位境界も提供します。 実験の結果,本アルゴリズムは確率環境と逆環境の両方で同時に学習でき,単一環境向けに設計された既存手法と比較して競合性が高いことがわかった。

関連論文リスト

• Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
  本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。 本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。 我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
  論文  参考訳（メタデータ） (2024-11-05T13:55:52Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring [46.30750729936261]
  敵環境における最適境界を実現するための最適化による探索(ExO)が提案された。 まず,ハイブリッド正規化器を用いたExOの新しいフレームワークと解析手法を構築した。 特に、$O(sum_a neq a* k2 log T / Delta_a)$で、$a*$は最適なアクションであり、$Delta_a$はアクションの亜最適ギャップである。
  論文  参考訳（メタデータ） (2024-02-13T09:34:22Z)
• Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
  対戦型オンラインマルチタスク強化学習環境について考察する。 K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。 学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
  論文  参考訳（メタデータ） (2023-01-11T02:18:26Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• Tractable Optimality in Episodic Latent MABs [75.17357040707347]
  我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。 エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。 我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
  論文  参考訳（メタデータ） (2022-10-05T22:53:46Z)
• Time Discretization-Invariant Safe Action Repetition for Policy Gradient Methods [43.49494338665518]
  政策勾配(PG)法に対する$delta$-invariantアルゴリズムを提案する。 我々の手法は$delta$-invariant だけでなく、強靭性も示しており、以前の$delta$-invariant アプローチよりも優れている。
  論文  参考訳（メタデータ） (2021-11-06T19:17:24Z)
• Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments [55.24895403089543]
  ドメインの一般化は、限られた数のトレーニング環境からのデータで、目に見えないテスト環境でうまく機能することを目的としています。 我々は,O(logd_s)$環境のみを見た後に一般化する予測器を高確率で生成することを保証する反復的特徴マッチングに基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-18T04:39:19Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Toward Adversarial Robustness via Semi-supervised Robust Training [93.36310070269643]
  アドリラルな例は、ディープニューラルネットワーク(DNN)に対する深刻な脅威であることが示されている。 R_stand$ と $R_rob$ の2つの異なるリスクを共同で最小化することで、新しい防御手法であるロバストトレーニング(RT)を提案する。
  論文  参考訳（メタデータ） (2020-03-16T02:14:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。