論文の概要: Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure

• arxiv url: http://arxiv.org/abs/2503.04010v1
• Date: Thu, 06 Mar 2025 01:51:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-07 15:57:47.859565
• Title: Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
• Title（参考訳）: 構造バンドのグリーディアルゴリズム:漸近的成功/失敗のシャープ特性
• Authors: Aleksandrs Slivkins, Yunzong Xu, Shiliang Zuo,
• Abstract要約: 我々は,既知報酬構造を持つバンドイット問題における欲求(探索のみ)アルゴリズムについて検討する。 我々は、グリディがアルゴリズム的に成功するか失敗するかを、サブ線形対線形後悔という意味で完全に特徴づける。 我々は、任意のフィードバックで、文脈的な包帯と対話的な意思決定に特徴を拡張します。
• 参考スコア（独自算出の注目度）: 51.4953549382486
• License:
• Abstract: We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure. We allow arbitrary finite reward structures, while prior work focused on a few specific ones. We fully characterize when the greedy algorithm asymptotically succeeds or fails, in the sense of sublinear vs. linear regret as a function of time. Our characterization identifies a partial identifiability property of the problem instance as the necessary and sufficient condition for the asymptotic success. Notably, once this property holds, the problem becomes easy -- any algorithm will succeed (in the same sense as above), provided it satisfies a mild non-degeneracy condition. We further extend our characterization to contextual bandits and interactive decision-making with arbitrary feedback, and demonstrate its broad applicability across various examples.
• Abstract（参考訳）: 我々は,既知報酬構造を持つバンドイット問題における欲求(探索のみ)アルゴリズムについて検討する。 任意の有限報酬構造を許容し、事前の作業はいくつかの特定のものに焦点を当てる。 時間の関数としての線形後悔と線形後悔の両面において、グリーディアルゴリズムが漸近的に成功するか失敗するかを完全に特徴づける。 本報告では, 問題インスタンスの部分的識別可能性特性を, 漸近的成功の必要十分条件として評価する。 特に、この性質が成り立つと、問題は容易になり、どんなアルゴリズムも(上と同じ意味で)成功し、穏やかな非退化条件を満たす。 さらに、任意のフィードバックで文脈的な帯域幅と対話的な意思決定に特徴を拡張し、その適用性を様々な例で示す。

関連論文リスト

• Agnostic Multi-Robust Learning Using ERM [19.313739782029185]
  頑健な学習における根本的な問題は非対称性である: 学習者は指数関数的に多くの摂動の全てを正しく分類する必要がある。 これとは対照的に、攻撃者は1つの摂動を成功させる必要がある。 本稿では,新しいマルチグループ設定を導入し,新しいマルチロバスト学習問題を提案する。
  論文  参考訳（メタデータ） (2023-03-15T21:30:14Z)
• Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits [27.09804256642197]
  我々はFrank-Wolfeアルゴリズムにインスパイアされたアルゴリズム群を紹介する。 我々は幅広い問題に対して新しい明示的アルゴリズムを構築した。 我々はこの現象を洞察に富んだおもちゃの問題で説明する。
  論文  参考訳（メタデータ） (2021-10-18T09:36:36Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• Structure Adaptive Algorithms for Stochastic Bandits [22.871155520200773]
  構造化多武装バンディット問題のクラスにおける報酬最大化について検討する。 平均的な武器の報酬は、与えられた構造的制約を満たす。 我々は、反復的なサドルポイントソルバを用いて、インスタンス依存の低バウンドからのアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-07-02T08:59:54Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)

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

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