論文の概要: Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality

• arxiv url: http://arxiv.org/abs/2006.08754v2
• Date: Fri, 23 Oct 2020 01:51:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 03:24:12.527622
• Title: Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
• Title（参考訳）: ペシミズムによるクルーシュ・オプティミズム:漸近的オプティミリティを超えた構造的バンド
• Authors: Kwang-Sung Jun, Chicheng Zhang
• Abstract要約: 我々は後悔を最小限に抑えるために構造化された包帯について研究する。 本稿では,有限仮説に焦点をあて,有界後悔を楽しみながら最適性を達成できるかを問う。
• 参考スコア（独自算出の注目度）: 25.627939043735683
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic structured bandits for minimizing regret. The fact that the popular optimistic algorithms do not achieve the asymptotic instance-dependent regret optimality (asymptotic optimality for short) has recently alluded researchers. On the other hand, it is known that one can achieve bounded regret (i.e., does not grow indefinitely with $n$) in certain instances. Unfortunately, existing asymptotically optimal algorithms rely on forced sampling that introduces an $\omega(1)$ term w.r.t. the time horizon $n$ in their regret, failing to adapt to the "easiness" of the instance. In this paper, we focus on the finite hypothesis case and ask if one can achieve the asymptotic optimality while enjoying bounded regret whenever possible. We provide a positive answer by introducing a new algorithm called CRush Optimism with Pessimism (CROP) that eliminates optimistic hypotheses by pulling the informative arms indicated by a pessimistic hypothesis. Our finite-time analysis shows that CROP $(i)$ achieves a constant-factor asymptotic optimality and, thanks to the forced-exploration-free design, $(ii)$ adapts to bounded regret, and $(iii)$ its regret bound scales not with $K$ but with an effective number of arms $K_\psi$ that we introduce. We also discuss a problem class where CROP can be exponentially better than existing algorithms in \textit{nonasymptotic} regimes. This problem class also reveals a surprising fact that even a clairvoyant oracle who plays according to the asymptotically optimal arm pull scheme may suffer a linear worst-case regret.
• Abstract（参考訳）: 後悔を最小限に抑えるために、確率的構成のバンディットを研究した。 一般的な楽観的アルゴリズムが漸近的なインスタンス依存的後悔の最適性(略して漸近的最適性)を達成できないという事実は、近年研究者をほのめかしている。 一方、ある場合において、有界な後悔(すなわち、$n$で無限に成長しない)を達成できることが知られている。 残念ながら、既存の漸近的最適アルゴリズムは、強制サンプリングに依存しており、それは$\omega(1)$ 項 w.r.t. the time horizon $n$ を後悔して導入し、インスタンスの "easiness" に適応できない。 本稿では,有限仮説に焦点をあて,可能な限り有界後悔を楽しみながら漸近的最適性を達成できるかを問う。 我々は、悲観的仮説によって示される情報的アームを引いて楽観的な仮説を除去するCROP(CRush Optimism with Pessimism)と呼ばれる新しいアルゴリズムを導入することで、肯定的な答えを提供する。 有限時間解析の結果、crop $は (i)$は定数要素の漸近最適性を達成し、強制探索のない設計のおかげで$ (ii)$ は限定された後悔に適応し、$ (iii)その後悔束のスケールは$K$ではなく、実際に紹介する腕数$K_\psi$である。 また,既存のアルゴリズムよりもCROPが指数関数的に優れている問題クラスについても論じる。 この問題クラスはまた、漸近的に最適なアームプルスキームに従ってプレーする透視性オラクルでさえ、線形最悪の後悔を被る可能性があるという驚くべき事実も明らかにしている。

関連論文リスト

• Optimal Batched Linear Bandits [9.795531604467406]
  本稿では,探索・推定・探索の枠組みを取り入れたバッチ線形バンドイト問題に対するE$4$アルゴリズムを提案する。 探索速度の適切な選択により、E$4$は、$O(loglog T)$バッチのみで有限時間ミニマックス最適後悔を達成する。 探索レートの別の選択で、E$4$は、少なくとも$O(log T)$バッチを必要とするインスタンス依存の後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2024-06-06T14:57:52Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory [30.061707627742766]
  適応性の強い概念であるインスタンス最適化を目指しており、どの問題の場合であっても、検討中のアルゴリズムは全ての一貫したアルゴリズムより優れていると主張する。 本稿では,一般関数近似を用いたインスタンス最適決定の非漸近的理論の開発に向けて第一歩を踏み出す。
  論文  参考訳（メタデータ） (2023-04-24T21:51:58Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality [39.2230418563572]
  意外なことに、最適有限時間後悔の概念は、この文脈で一意に定義された性質ではない。 半最適後悔を有限時間・経時的に認めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-20T22:11:08Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Predictive Power of Nearest Neighbors Algorithm under Random Perturbation [21.79888306754263]
  古典的な$k$Nearest Neighbors(k$-NN)におけるデータ破損シナリオについて検討する。 このようなシナリオでは、後悔に対する汚職レベルの影響を慎重に評価する。
  論文  参考訳（メタデータ） (2020-02-13T01:35:35Z)

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

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