論文の概要: Differentiable Linear Bandit Algorithm

• arxiv url: http://arxiv.org/abs/2006.03000v1
• Date: Thu, 4 Jun 2020 16:43:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-25 08:57:46.442549
• Title: Differentiable Linear Bandit Algorithm
• Title（参考訳）: 微分可能な線形バンディットアルゴリズム
• Authors: Kaige Yang and Laura Toni
• Abstract要約: アッパー信頼境界は、線形多腕バンディット問題の最も一般的な方法である。 勾配上昇による信頼度を学習できる勾配推定器を導入する。 提案アルゴリズムは,腕の特徴の次元を$d$で,信頼度を$hatbeta$で学習したサイズを$tildemathcalO(hatbetasqrtdT)$上限とする。
• 参考スコア（独自算出の注目度）: 6.849358422233866
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Upper Confidence Bound (UCB) is arguably the most commonly used method for linear multi-arm bandit problems. While conceptually and computationally simple, this method highly relies on the confidence bounds, failing to strike the optimal exploration-exploitation if these bounds are not properly set. In the literature, confidence bounds are typically derived from concentration inequalities based on assumptions on the reward distribution, e.g., sub-Gaussianity. The validity of these assumptions however is unknown in practice. In this work, we aim at learning the confidence bound in a data-driven fashion, making it adaptive to the actual problem structure. Specifically, noting that existing UCB-typed algorithms are not differentiable with respect to confidence bound, we first propose a novel differentiable linear bandit algorithm. Then, we introduce a gradient estimator, which allows the confidence bound to be learned via gradient ascent. Theoretically, we show that the proposed algorithm achieves a $\tilde{\mathcal{O}}(\hat{\beta}\sqrt{dT})$ upper bound of $T$-round regret, where $d$ is the dimension of arm features and $\hat{\beta}$ is the learned size of confidence bound. Empirical results show that $\hat{\beta}$ is significantly smaller than its theoretical upper bound and proposed algorithms outperforms baseline ones on both simulated and real-world datasets.
• Abstract（参考訳）: アッパー信頼境界 (UCB) は、線形多腕バンディット問題において最もよく用いられる手法である。 概念的にも計算的にも単純であるが、この手法は信頼境界に強く依存しており、これらの境界が適切に設定されていない場合、最適な探索・探索を行えない。 文献では、信頼境界は典型的には、報酬分布の仮定に基づく濃度不等式(例えば、サブガウシアン性)から導かれる。 しかし、これらの仮定の妥当性は実際には不明である。 本研究では,データ駆動方式の信頼性を学習し,実際の問題構造に適応させることを目的とする。 具体的には、既存のucb型アルゴリズムが信頼度境界に関して微分可能ではないことを指摘し、まず新しい微分可能線形バンディットアルゴリズムを提案する。 次に勾配推定器を導入し、勾配上昇を通じて信頼度を学習できるようにする。 理論的には、提案アルゴリズムが$\tilde{\mathcal{O}}(\hat{\beta}\sqrt{dT})$上界の$T$の後悔を達成し、$d$は腕の特徴の次元であり、$\hat{\beta}$は信頼境界の学習されたサイズであることを示す。 実験の結果、$\hat{\beta}$は理論上界よりもかなり小さく、提案アルゴリズムはシミュレーションと実世界の両方のデータセットでベースラインよりも優れていることがわかった。

関連論文リスト

• Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates [7.21848268647674]
  我々は、決定のための$varepsilon$-greedybanditアルゴリズムと、疎帯域パラメータを推定するためのハードしきい値アルゴリズムを統合する。 マージン条件下では、我々の手法は、$O(T1/2)$ regret あるいは古典的な$O(T1/2)$-consistent推論のいずれかを達成する。
  論文  参考訳（メタデータ） (2024-11-10T01:47:11Z)
• Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization [15.275864909088577]
  事前の未知のノイズレベルに適応することは、シーケンシャルな意思決定において非常に重要であるが難しい問題である。 未知のガウスパラメータ $sigma_*2$ に半適応的な新しい信頼集合を提案する。 有界報酬に対しては,先行技術により数値性能が大幅に向上した新しい分散適応信頼セットを提案する。
  論文  参考訳（メタデータ） (2024-02-12T00:19:09Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification [0.0]
  固定誤差率$delta$(固定信頼度Top-m識別)の下で最大の手段を持つmアームの識別問題について検討する。 この問題は、特に医療やレコメンデーションシステムにおける実践的な応用によって動機付けられている。
  論文  参考訳（メタデータ） (2021-11-02T10:27:17Z)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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