論文の概要: Bandit and Delayed Feedback in Online Structured Prediction

• arxiv url: http://arxiv.org/abs/2502.18709v1
• Date: Wed, 26 Feb 2025 00:00:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-27 14:59:13.988004
• Title: Bandit and Delayed Feedback in Online Structured Prediction
• Title（参考訳）: オンライン構造化予測における帯域と遅延フィードバック
• Authors: Yuki Shibukawa, Taira Tsuchiya, Shinsaku Sakaue, Kenji Yamanishi,
• Abstract要約: 要求の少ないフィードバック、帯域幅、遅延フィードバックを扱うアルゴリズムを提案する。 バンディットフィードバックを用いたオンライン分類において,提案アルゴリズムの性能を数値的に評価する。
• 参考スコア（独自算出の注目度）: 25.637979150499874
• License:
• Abstract: Online structured prediction is a task of sequentially predicting outputs with complex structures based on inputs and past observations, encompassing online classification. Recent studies showed that in the full information setup, we can achieve finite bounds on the surrogate regret, i.e., the extra target loss relative to the best possible surrogate loss. In practice, however, full information feedback is often unrealistic as it requires immediate access to the whole structure of complex outputs. Motivated by this, we propose algorithms that work with less demanding feedback, bandit and delayed feedback. For the bandit setting, using a standard inverse-weighted gradient estimator, we achieve a surrogate regret bound of $O(\sqrt{KT})$ for the time horizon $T$ and the size of the output set $K$. However, $K$ can be extremely large when outputs are highly complex, making this result less desirable. To address this, we propose an algorithm that achieves a surrogate regret bound of $O(T^{2/3})$, which is independent of $K$. This is enabled with a carefully designed pseudo-inverse matrix estimator. Furthermore, for the delayed full information feedback setup, we obtain a surrogate regret bound of $O(D^{2/3} T^{1/3})$ for the delay time $D$. We also provide algorithms for the delayed bandit feedback setup. Finally, we numerically evaluate the performance of the proposed algorithms in online classification with bandit feedback.
• Abstract（参考訳）: オンライン構造化予測は、入力と過去の観察に基づいて複雑な構造を持つ出力を逐次予測するタスクであり、オンライン分類を含んでいる。 近年の研究では、全ての情報設定において、サロゲートの後悔、すなわち最高のサロゲートの損失に対する余分な目標損失について有限限の限界を達成できることが示されている。 しかし実際には、複雑な出力の構造全体への即時アクセスを必要とするため、完全な情報フィードバックは非現実的であることが多い。 そこで我々は,要求の少ないフィードバックや帯域幅,遅延フィードバックを扱うアルゴリズムを提案する。 バンドイット設定では、標準逆重み付き勾配推定器を用いて、時間地平線$T$と出力セット$K$に対して$O(\sqrt{KT})$のサロゲート後悔境界を達成する。 しかし、出力が非常に複雑である場合、$K$は非常に大きくなり、その結果が望ましくない。 これを解決するために,$K$に依存しない$O(T^{2/3})$のサロゲート後悔境界を実現するアルゴリズムを提案する。 これは、慎重に設計された擬似逆行列推定器によって実現される。 さらに、遅延した全情報フィードバック設定に対しては、遅延時間$D$に対して$O(D^{2/3} T^{1/3})のサロゲート後悔境界を求める。 また,遅延帯域フィードバック設定のためのアルゴリズムも提供する。 最後に,バンディットフィードバックを用いたオンライン分類において,提案アルゴリズムの性能を数値的に評価する。

関連論文リスト

• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  遅延フィードバックを伴うバンド凸最適化(BCO)。 我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。 提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
  論文  参考訳（メタデータ） (2024-02-14T13:08:26Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays [24.998122268199797]
  本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。 我々のアルゴリズムは任意の過剰な遅延を許容し、$T$をオーダーすることができる。
  論文  参考訳（メタデータ） (2023-08-21T12:17:40Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• Nonstochastic Bandits with Composite Anonymous Feedback [41.38921728211769]
  本研究では,アクションの損失が直ちにプレイヤーに請求されない非確率的バンディット設定について検討する。 各ラウンドの最後にプレイヤーが観測した瞬間的な損失は、これまでプレイされたアクションの多くの損失成分の合計である。
  論文  参考訳（メタデータ） (2021-12-06T08:44:04Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  GPバンディットアルゴリズムの残差境界と後部分布の複雑さのトレードオフを特徴付ける方法を示す。 大域的最適化に応用したGPバンディットアルゴリズムの精度と複雑性のトレードオフを観察する。
  論文  参考訳（メタデータ） (2020-03-23T21:05:15Z)

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

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