論文の概要: Leveraging Initial Hints for Free in Stochastic Linear Bandits

• arxiv url: http://arxiv.org/abs/2203.04274v1
• Date: Tue, 8 Mar 2022 18:48:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-09 16:12:54.916269
• Title: Leveraging Initial Hints for Free in Stochastic Linear Bandits
• Title（参考訳）: 確率線形帯域における初期ヒントフリー化
• Authors: Ashok Cutkosky, Chris Dann, Abhimanyu Das, Qiuyi (Richard) Zhang
• Abstract要約: 本研究では,学習者の事前知識を付加した帯域フィードバックによる最適化の設定について,最適行動の最初のヒントとして検討する。 我々は、このヒントを用いて、ヒントが正確である場合にその後悔を$tilde O(sqrtT)$に改善する新しいアルゴリズムを提案する。 おそらく驚くべきことに、私たちの研究は、最悪のパフォーマンスを犠牲にすることなく、ヒントを活用することで、証明可能な利益が得られていることを示している。
• 参考スコア（独自算出の注目度）: 38.58449930961883
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the setting of optimizing with bandit feedback with additional prior knowledge provided to the learner in the form of an initial hint of the optimal action. We present a novel algorithm for stochastic linear bandits that uses this hint to improve its regret to $\tilde O(\sqrt{T})$ when the hint is accurate, while maintaining a minimax-optimal $\tilde O(d\sqrt{T})$ regret independent of the quality of the hint. Furthermore, we provide a Pareto frontier of tight tradeoffs between best-case and worst-case regret, with matching lower bounds. Perhaps surprisingly, our work shows that leveraging a hint shows provable gains without sacrificing worst-case performance, implying that our algorithm adapts to the quality of the hint for free. We also provide an extension of our algorithm to the case of $m$ initial hints, showing that we can achieve a $\tilde O(m^{2/3}\sqrt{T})$ regret.
• Abstract（参考訳）: 本研究では,学習者に与えられた事前知識を付加したバンディットフィードバックによる最適化の設定を,最適動作の初期ヒントとして検討する。 我々は、このヒントを用いて、その後悔を$\tilde O(\sqrt{T})$に改善し、そのヒントが正確である場合に、最小値最適化$\tilde O(d\sqrt{T})$後悔を、そのヒントの品質によらず維持する新しいアルゴリズムを提案する。 さらに、ベストケースと最悪のケースの後悔の間の緊密なトレードオフのパレートフロンティアも提供します。 おそらく意外なことに、私たちの研究は、ヒントを活用することで最悪のパフォーマンスを犠牲にすることなく、証明可能な利益が得られることを示している。 また、$m$の初期ヒントの場合にアルゴリズムの拡張を提供し、$\tilde o(m^{2/3}\sqrt{t})$ regret が達成できることを示します。

関連論文リスト

• Incentive-compatible Bandits: Importance Weighting No More [14.344759978208957]
  本稿では,包括的フィードバックによるインセンティブ適合型オンライン学習の課題について検討する。 この研究では、最初のインセンティブに適合するアルゴリズムを提案し、$O(sqrtKT)$ regret bounds を楽しむ。
  論文  参考訳（メタデータ） (2024-05-10T13:57:13Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
  論文  参考訳（メタデータ） (2021-10-15T12:32:33Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Multinomial Logit Contextual Bandits: Provable Optimality and Practicality [15.533842336139063]
  パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。 本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。 本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
  論文  参考訳（メタデータ） (2021-03-25T15:42:25Z)
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition [37.6975819766632]
  我々は、敵対コストと既知の移行で最短経路問題を研究します。 ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T20:55:28Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。 有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。 我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
  論文  参考訳（メタデータ） (2020-07-13T16:30:47Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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