論文の概要: Online Learning with Sublinear Best-Action Queries
- arxiv url: http://arxiv.org/abs/2407.16355v1
- Date: Tue, 23 Jul 2024 09:59:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 17:45:51.872237
- Title: Online Learning with Sublinear Best-Action Queries
- Title（参考訳）: サブ線形Best-Action Queriesを用いたオンライン学習
- Authors: Matteo Russo, Andrea Celli, Riccardo Colini Baldeschi, Federico Fusco, Daniel Haimovich, Dima Karamshuk, Stefano Leonardi, Niek Tax,
- Abstract要約: 本研究では,与えられた時間ステップにおける最善の行動の識別を事前に明らかにする,emphbest-actionクエリのパワーについて検討する。
完全なフィードバックモデルでは、$k$クエリは$Thetaleft(minleftsqrt T, frac Tkrightright)$の最適後悔を達成するのに十分である。
- 参考スコア（独自算出の注目度）: 15.625072719419727
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In online learning, a decision maker repeatedly selects one of a set of actions, with the goal of minimizing the overall loss incurred. Following the recent line of research on algorithms endowed with additional predictive features, we revisit this problem by allowing the decision maker to acquire additional information on the actions to be selected. In particular, we study the power of \emph{best-action queries}, which reveal beforehand the identity of the best action at a given time step. In practice, predictive features may be expensive, so we allow the decision maker to issue at most $k$ such queries. We establish tight bounds on the performance any algorithm can achieve when given access to $k$ best-action queries for different types of feedback models. In particular, we prove that in the full feedback model, $k$ queries are enough to achieve an optimal regret of $\Theta\left(\min\left\{\sqrt T, \frac Tk\right\}\right)$. This finding highlights the significant multiplicative advantage in the regret rate achievable with even a modest (sublinear) number $k \in \Omega(\sqrt{T})$ of queries. Additionally, we study the challenging setting in which the only available feedback is obtained during the time steps corresponding to the $k$ best-action queries. There, we provide a tight regret rate of $\Theta\left(\min\left\{\frac{T}{\sqrt k},\frac{T^2}{k^2}\right\}\right)$, which improves over the standard $\Theta\left(\frac{T}{\sqrt k}\right)$ regret rate for label efficient prediction for $k \in \Omega(T^{2/3})$.
- Abstract（参考訳）: オンライン学習において、意思決定者は一連の行動の1つを繰り返し選択し、全体の損失を最小限にすることを目的としている。
新たな予測機能を備えたアルゴリズムに関する最近の研究の行に続いて、意思決定者が選択すべき行動に関する追加情報を取得することによって、この問題を再考する。
特に,与えられた時間ステップにおける最善の行動の識別を事前に示す「emph{best-action query}」のパワーについて検討する。
実際には、予測機能は高価である可能性があるため、意思決定者はそのようなクエリを少なくとも$kで発行することができる。
異なるタイプのフィードバックモデルに対して、$k$のベストアクションクエリが与えられたとき、任意のアルゴリズムが達成できるパフォーマンスに厳密な境界を確立する。
特に、完全なフィードバックモデルでは、$k$クエリは$\Theta\left(\min\left\{\sqrt T, \frac Tk\right\}\right)$の最適後悔を達成するのに十分であることを示す。
この発見は、モデスト(サブリニア)番号$k \in \Omega(\sqrt{T})$でさえも達成可能な後悔率において、大きな乗法的優位性を浮き彫りにしている。
さらに、$k$のベストアクションクエリに対応する時間ステップでのみ利用可能なフィードバックを得るという難易度設定についても検討する。
ここでは、$\Theta\left(\min\left\{\frac{T}{\sqrt k},\frac{T^2}{k^2}\right\right)$の厳密な後悔率を提供し、標準の$\Theta\left(\frac{T}{\sqrt k}\right)$ $k \in \Omega(T^{2/3})$に対するラベル効率予測の後悔率を改善する。
関連論文リスト
- Learning Thresholds with Latent Values and Censored Feedback [18.129896050051432]
未知の報酬$g(gamma, v)$が提案されたしきい値$gamma$と潜伏値$v$に依存する問題を示し、そのしきい値が未知の潜伏値よりも低い場合のみ$$を達成できる。
この問題は、オンラインオークションにおける予約価格の最適化、クラウドソーシングにおけるオンラインタスクの割り当て、雇用におけるリクルートバーの設定など、現実的なシナリオにおける幅広い応用がある。
論文 参考訳（メタデータ） (2023-12-07T19:30:08Z) - Contextual Bandits and Imitation Learning via Preference-Based Active
Queries [17.73844193143454]
本研究では,学習者が実行された行動報酬の直接的な知識を欠いている文脈的包帯と模倣学習の問題を考察する。
その代わり、学習者は各ラウンドのエキスパートに積極的に問い合わせて2つのアクションを比較し、ノイズの多い好みのフィードバックを受け取ることができる。
学習者の目的は、実行されたアクションに関連する後悔を最小限に抑えると同時に、専門家が行った比較クエリの数を最小化することである。
論文 参考訳（メタデータ） (2023-07-24T16:36:04Z) - Non-stationary Projection-free Online Learning with Dynamic and Adaptive
Regret Guarantees [36.746745619968024]
本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。
我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。
本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
論文 参考訳（メタデータ） (2023-05-19T15:02:10Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。
時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。
また, 動的上界に依存した新しい行列不等式濃度を証明した。
論文 参考訳（メタデータ） (2021-10-15T12:32:33Z) - Multinomial Logit Contextual Bandits: Provable Optimality and
Practicality [15.533842336139063]
パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。
本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。
本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
論文 参考訳（メタデータ） (2021-03-25T15:42:25Z) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳（メタデータ） (2021-03-21T11:43:35Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Online Learning with Imperfect Hints [72.4277628722419]
オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。
我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
論文 参考訳（メタデータ） (2020-02-11T23:06:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。