論文の概要: High-Dimensional Experimental Design and Kernel Bandits

• arxiv url: http://arxiv.org/abs/2105.05806v1
• Date: Wed, 12 May 2021 17:10:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-13 12:19:00.841851
• Title: High-Dimensional Experimental Design and Kernel Bandits
• Title（参考訳）: 高次元実験設計とカーネルバンド
• Authors: Romain Camilleri and Julian Katz-Samuels and Kevin Jamieson
• Abstract要約: 最適な線形実験設計の手法を利用して、線形バンディットの最先端の結果を得ています。 G$-optimal designのような目的から返される設計は、実際に潜在的な測定ベクトルのプール上の確率分布である。 我々は、次元 $d$ に対する任意の依存から$n$ を解放する丸め手順を提案する。
• 参考スコア（独自算出の注目度）: 9.401375475860561
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years methods from optimal linear experimental design have been leveraged to obtain state of the art results for linear bandits. A design returned from an objective such as $G$-optimal design is actually a probability distribution over a pool of potential measurement vectors. Consequently, one nuisance of the approach is the task of converting this continuous probability distribution into a discrete assignment of $N$ measurements. While sophisticated rounding techniques have been proposed, in $d$ dimensions they require $N$ to be at least $d$, $d \log(\log(d))$, or $d^2$ based on the sub-optimality of the solution. In this paper we are interested in settings where $N$ may be much less than $d$, such as in experimental design in an RKHS where $d$ may be effectively infinite. In this work, we propose a rounding procedure that frees $N$ of any dependence on the dimension $d$, while achieving nearly the same performance guarantees of existing rounding procedures. We evaluate the procedure against a baseline that projects the problem to a lower dimensional space and performs rounding which requires $N$ to just be at least a notion of the effective dimension. We also leverage our new approach in a new algorithm for kernelized bandits to obtain state of the art results for regret minimization and pure exploration. An advantage of our approach over existing UCB-like approaches is that our kernel bandit algorithms are also robust to model misspecification.
• Abstract（参考訳）: 近年, 最適線形実験設計の手法が活用され, 線形バンディットの最先端技術が得られるようになった。 G$-optimalデザインのような目的から返される設計は、実際にはポテンシャル測定ベクトルのプール上の確率分布である。 したがって、このアプローチの1つのニュアンスは、この連続確率分布を$N$の測定の離散代入に変換するタスクである。 洗練された丸め技術が提案されているが、$d$次元では、少なくとも$d$, $d \log(\log(d))$, $d^2$は解の準最適性に基づいて必要である。 この論文では、RKHSの実験的な設計のように、$N$が$d$よりもはるかに小さいかもしれない設定に興味があります。 本研究では,従来の丸め手順とほぼ同じ性能保証を達成しつつ,次元$d$への依存を解放する丸め手順を提案する。 我々は,問題を低次元空間に投影し,少なくとも実効次元の概念として$N$を必要とするラウンドリングを行うベースラインに対する手続きを評価する。 我々はまた,新たな手法をカーネル化されたバンディットのための新しいアルゴリズムで活用し,後悔の最小化と純粋な探索のための最先端の成果を得る。 既存のucbのようなアプローチに対する我々のアプローチの利点は、カーネルバンディットアルゴリズムがモデルの誤特定にも頑健であることです。

関連論文リスト

• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
  線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。 特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。 提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
  論文  参考訳（メタデータ） (2020-11-02T14:59:39Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)

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

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