論文の概要: Linear Bandits with Partially Observable Features
- arxiv url: http://arxiv.org/abs/2502.06142v1
- Date: Mon, 10 Feb 2025 04:15:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:35:08.276401
- Title: Linear Bandits with Partially Observable Features
- Title(参考訳): 部分観察可能な特徴を持つ線形帯域
- Authors: Wonyoung Kim, Sungwoo Park, Garud Iyengar, Assaf Zeevi, Min-hwan Oh,
- Abstract要約: 本稿では,部分的に観測可能な特徴を持つ線形帯域問題を導入し,部分的な報奨情報と突発的な推定を行う。
遅延部分に対する適切なアドレスがなければ、後悔は、報酬に対する影響が不明であるため、決定の地平線上で線形に増加する可能性がある。
本稿では,潜在特徴を扱うための新しい解析法と,サブ線形後悔を実現するアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 35.08645010112184
- License:
- Abstract: We introduce a novel linear bandit problem with partially observable features, resulting in partial reward information and spurious estimates. Without proper address for latent part, regret possibly grows linearly in decision horizon $T$, as their influence on rewards are unknown. To tackle this, we propose a novel analysis to handle the latent features and an algorithm that achieves sublinear regret. The core of our algorithm involves (i) augmenting basis vectors orthogonal to the observed feature space, and (ii) introducing an efficient doubly robust estimator. Our approach achieves a regret bound of $\tilde{O}(\sqrt{(d + d_h)T})$, where $d$ is the dimension of observed features, and $d_h$ is the unknown dimension of the subspace of the unobserved features. Notably, our algorithm requires no prior knowledge of the unobserved feature space, which may expand as more features become hidden. Numerical experiments confirm that our algorithm outperforms both non-contextual multi-armed bandits and linear bandit algorithms depending solely on observed features.
- Abstract(参考訳): 本稿では,部分的に観測可能な特徴を持つ線形帯域問題を導入し,部分的な報奨情報と突発的な推定を行う。
遅延部分に対する適切なアドレスがなければ、後悔は、報酬に対する影響が不明であるため、決定の地平線上で線形に増加する可能性がある。
そこで本研究では,潜在特徴を扱うための新しい解析法と,サブ線形後悔を実現するアルゴリズムを提案する。
私たちのアルゴリズムのコアは
一 観測された特徴空間に直交する基底ベクトルを増大させ、
(二)効率的な二重頑健な推定器を導入すること。
我々のアプローチは、$\tilde{O}(\sqrt{(d + d_h)T})$の後悔境界を達成し、$d$は観測された特徴の次元であり、$d_h$は観測されていない特徴の部分空間の未知次元である。
特に、我々のアルゴリズムでは、観測されていない特徴空間に関する事前の知識は必要とせず、より多くの特徴が隠されるにつれて拡張される可能性がある。
数値実験により,本アルゴリズムは観測された特徴のみによらず,非テクスチュアルなマルチアームバンディットと線形バンディットのアルゴリズムよりも優れていることを確認した。
関連論文リスト
- Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳(メタデータ) (2024-03-15T23:36:55Z) - Learning Adversarial Low-rank Markov Decision Processes with Unknown
Transition and Full-information Feedback [30.23951525723659]
本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。
政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
論文 参考訳(メタデータ) (2023-11-14T03:12:43Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳(メタデータ) (2023-03-17T17:53:28Z) - Exploration in Linear Bandits with Rich Action Sets and its Implications
for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。
本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文 参考訳(メタデータ) (2022-07-23T20:25:07Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳(メタデータ) (2021-07-12T21:30:41Z) - High-Dimensional Sparse Linear Bandits [67.9378546011416]
データ・ポーア・システマティクスにおける疎線形包帯に対して、新しい$Omega(n2/3)$ dimension-free minimax regret lower boundを導出する。
また、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$O(sqrtn)$ regret上界も証明する。
論文 参考訳(メタデータ) (2020-11-08T16:48:11Z) - Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。
特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。
提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
論文 参考訳(メタデータ) (2020-11-02T14:59:39Z) - Sparsity-Agnostic Lasso Bandit [27.383079108028074]
特徴ベクトルの次元$d$が潜在的に大きいような文脈的包帯問題を考える。
スパースブレイディットのための既存のアルゴリズムはすべて、スパーシティインデックス$s_$の値に関する事前知識を必要とする。
本稿では,スパーシティ指数$s_$の事前知識を必要としないアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-16T17:24:12Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳(メタデータ) (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。