論文の概要: Greedy Algorithm almost Dominates in Smoothed Contextual Bandits

• arxiv url: http://arxiv.org/abs/2005.10624v2
• Date: Mon, 27 Dec 2021 18:30:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-01 13:21:06.883990
• Title: Greedy Algorithm almost Dominates in Smoothed Contextual Bandits
• Title（参考訳）: Smoothed Contextual Banditsにおけるグリーディアルゴリズムの優位性
• Authors: Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, Zhiwei Steven Wu
• Abstract要約: オンライン学習アルゴリズムは探索と搾取のバランスをとる必要がある。 欲求的アプローチは、他のアルゴリズムのベイズ的後悔率とほぼ一致していることを示す。
• 参考スコア（独自算出の注目度）: 100.09904315064372
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online learning algorithms, widely used to power search and content optimization on the web, must balance exploration and exploitation, potentially sacrificing the experience of current users in order to gain information that will lead to better decisions in the future. While necessary in the worst case, explicit exploration has a number of disadvantages compared to the greedy algorithm that always "exploits" by choosing an action that currently looks optimal. We ask under what conditions inherent diversity in the data makes explicit exploration unnecessary. We build on a recent line of work on the smoothed analysis of the greedy algorithm in the linear contextual bandits model. We improve on prior results to show that a greedy approach almost matches the best possible Bayesian regret rate of any other algorithm on the same problem instance whenever the diversity conditions hold, and that this regret is at most $\tilde O(T^{1/3})$.
• Abstract（参考訳）: Web上の検索とコンテンツの最適化に広く使われているオンライン学習アルゴリズムは、探索とエクスプロイトのバランスを保ち、将来のより良い意思決定につながる情報を得るために、現在のユーザの経験を犠牲にする可能性がある。 最悪の場合、明示的な探索は、現在最適に見えるアクションを選択することで常に「探索する」という欲求アルゴリズムと比較して、多くの欠点がある。 我々は、データに固有の多様性が明示的な探索を不要にする条件について尋ねる。 本稿では,線形文脈バンディットモデルにおけるグリーディアルゴリズムの平滑化解析に関する最近の研究を基礎としている。 我々は、同じ問題インスタンス上の他のアルゴリズムが持つ最善のベイズ的後悔率とほぼ一致し、この後悔が少なくとも$\tilde o(t^{1/3})$であることを示すために、事前の結果を改善した。

関連論文リスト

• Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions [98.75618795470524]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-13T17:58:58Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Algorithmic Challenges in Ensuring Fairness at the Time of Decision [6.228560624452748]
  社会的文脈におけるアルゴリズムによる意思決定は、帯域幅フィードバックの下で最適化される。 最近の訴訟は、アルゴリズムによる価格設定の慣行を展開している企業を非難している。 凸最適化の文脈において、遠心自由というよく研究された公正性の概念を導入する。
  論文  参考訳（メタデータ） (2021-03-16T19:06:28Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits [43.03669155559218]
  我々は、あるしきい値を超える関数値が「十分良い」という緩和された最適化基準の下で、ガウス過程(GP)バンディットの問題を研究する。 実用面では、既知のしきい値に従って1つの「良い行動」を見つけることの問題を考えるとともに、しきい値の知識を生かしたいくつかの善行動識別アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2021-02-11T01:16:58Z)
• Be Greedy in Multi-Armed Bandits [22.301793734117805]
  グレディアルゴリズムは、各ラウンドで局所最適選択を行う、シーケンシャルな決定問題の最も単純なものである。 We provide a generic worst-case bound on the regret of the Greedy algorithm。 連続・無限・多武装バンディット問題において,ほぼ最適の最悪の後悔境界を検証できることを証明した。
  論文  参考訳（メタデータ） (2021-01-04T16:47:02Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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