論文の概要: Norm-Agnostic Linear Bandits

• arxiv url: http://arxiv.org/abs/2205.01257v1
• Date: Tue, 3 May 2022 00:55:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-04 13:00:21.753457
• Title: Norm-Agnostic Linear Bandits
• Title（参考訳）: Norm-Agnostic Linear Bandits
• Authors: Spencer (Brady) Gales, Sunder Sethuraman, Kwang-Sung Jun
• Abstract要約: 本稿では,そのような知識を初めて必要としない新しいアルゴリズムを提案する。 我々は、その遺言を解析する。一つは、変更アームセット設定用、もう一つは固定アームセット設定用である。 我々の数値実験は、標準的なアルゴリズムが$|theta*|le S$が正しくない場合に、$S$の知識が破滅的に失敗する可能性があることを仮定している。
• 参考スコア（独自算出の注目度）: 9.700635713828698
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear bandits have a wide variety of applications including recommendation systems yet they make one strong assumption: the algorithms must know an upper bound $S$ on the norm of the unknown parameter $\theta^*$ that governs the reward generation. Such an assumption forces the practitioner to guess $S$ involved in the confidence bound, leaving no choice but to wish that $\|\theta^*\|\le S$ is true to guarantee that the regret will be low. In this paper, we propose novel algorithms that do not require such knowledge for the first time. Specifically, we propose two algorithms and analyze their regret bounds: one for the changing arm set setting and the other for the fixed arm set setting. Our regret bound for the former shows that the price of not knowing $S$ does not affect the leading term in the regret bound and inflates only the lower order term. For the latter, we do not pay any price in the regret for now knowing $S$. Our numerical experiments show standard algorithms assuming knowledge of $S$ can fail catastrophically when $\|\theta^*\|\le S$ is not true whereas our algorithms enjoy low regret.
• Abstract（参考訳）: 線形帯域は、リコメンデーションシステムを含む幅広い応用を持つが、強い仮定を下す: アルゴリズムは、報酬生成を支配する未知のパラメータ $\theta^*$ のノルム上で上限の$S$を知っていなければならない。 そのような仮定は、実践者が信頼境界に関わった$S$を推測することを強制し、$\|\theta^*\|\le S$が後悔が低いことを保証してくれることを願う以外選択肢を残さない。 本稿では,そのような知識を初めて必要としない新しいアルゴリズムを提案する。 具体的には,2つのアルゴリズムを提案し,その後悔の限界を分析する。1つはアームセットの変更,もう1つは固定アームセットの設定である。 我々の前者に対する後悔は、S$を知らないという価格が後悔境界の先頭項に影響せず、下位項のみを膨らませていることを示している。 後者については、現在S$を知っていることを後悔して、いかなる代償も払わない。 我々の数値実験では、$s$ の知識を仮定した標準的なアルゴリズムは、$\|\theta^*\|\le s$ が正しくないときに破滅的に失敗する可能性がある。

関連論文リスト

• Near-optimal Per-Action Regret Bounds for Sleeping Bandits [8.261117235807607]
  睡眠中の包帯に対して, 行動毎のほぼ最適な後悔境界を導出する。 合計で$K$、最大で$A$の武器が各ラウンドで$T$以上の場合、最もよく知られている上限は$O(KsqrtTAlnK)$である。 本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
  論文  参考訳（メタデータ） (2024-03-02T21:22:46Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Non-Stationary Dueling Bandits [8.298716599039501]
  我々は、非定常デュエルバンディット問題をK$アームで研究し、タイムホライズメント$T$は、固定セグメント$M$からなる。 蓄積した後悔を最小限に抑えるため、学習者は各定常セグメントのコンドルチェットの勝者をできるだけ頻繁に選ぶ必要がある。 我々は、M$やT$の知識を必要とせず、非定常ケースに対する後悔の意を示す。
  論文  参考訳（メタデータ） (2022-02-02T09:57:35Z)
• 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)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
  低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。 低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-04T15:30:14Z)
• Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits [20.207989166682832]
  2つの一般的な線形バンディット設定におけるモデル選択の問題について考察する。 まず、[K]$におけるarm $iの平均的な報酬は、$mu_i+ langle alpha_i,t,theta*|$である。 我々は、ALBが$O(|theta*|sqrtT)$の後悔のスケーリングを達成することを示す。
  論文  参考訳（メタデータ） (2020-06-04T02:19:00Z)

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

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