論文の概要: Online Linear Optimization with Many Hints

• arxiv url: http://arxiv.org/abs/2010.03082v1
• Date: Tue, 6 Oct 2020 23:25:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 07:50:58.247262
• Title: Online Linear Optimization with Many Hints
• Title（参考訳）: 多くのヒントによるオンライン線形最適化
• Authors: Aditya Bhaskara and Ashok Cutkosky and Ravi Kumar and Manish Purohit
• Abstract要約: 本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。 この設定では、コストベクトルと正の相関を持つ$K$ヒントの凸結合が存在する場合、対数後悔を求めるアルゴリズムを考案する。
• 参考スコア（独自算出の注目度）: 72.4277628722419
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study an online linear optimization (OLO) problem in which the learner is provided access to $K$ "hint" vectors in each round prior to making a decision. In this setting, we devise an algorithm that obtains logarithmic regret whenever there exists a convex combination of the $K$ hints that has positive correlation with the cost vectors. This significantly extends prior work that considered only the case $K=1$. To accomplish this, we develop a way to combine many arbitrary OLO algorithms to obtain regret only a logarithmically worse factor than the minimum regret of the original algorithms in hindsight; this result is of independent interest.
• Abstract（参考訳）: 本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。 この設定では、コストベクトルと正の相関を持つ$k$ヒントの凸結合が存在する場合、対数的後悔を得るアルゴリズムを考案する。 これは、$K=1$の場合にのみ考慮する以前の作業を大幅に拡張する。 そこで本研究では,多くの任意のOLOアルゴリズムを組み合わせることで,後続のアルゴリズムに対する最小の後悔よりも,対数的に悪い要因のみを求める方法を開発した。

関連論文リスト

• Infrequent Resolving Algorithm for Online Linear Programming [3.247415064064425]
  既存のオンライン線形プログラミング(OLP)アルゴリズムは、LPベースアルゴリズムとLPフリーアルゴリズムの2つのカテゴリに分類される。 本稿では,LPを時間的水平線上でのO(loglog T)$倍だけ解きながら,常に後悔するアルゴリズムを提案する。 我々のアルゴリズムは、LPの$O(loglog T)$ timesと$Oleft(T(1/2+epsilon)Mright)$ regretを、LPの$M$ timesを解くことで、絶え間ない後悔を保証できる。
  論文  参考訳（メタデータ） (2024-08-01T11:09:01Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• 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)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
  線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。 まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。 次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
  論文  参考訳（メタデータ） (2020-07-23T08:23:44Z)
• Online Learning with Imperfect Hints [72.4277628722419]
  オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。 我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
  論文  参考訳（メタデータ） (2020-02-11T23:06:09Z)

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

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