論文の概要: Stochastic Linear Bandits with Protected Subspace

• arxiv url: http://arxiv.org/abs/2011.01016v2
• Date: Mon, 1 Mar 2021 21:40:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-30 12:31:36.363125
• Title: Stochastic Linear Bandits with Protected Subspace
• Title（参考訳）: 保護部分空間を持つ確率線形帯域
• Authors: Advait Parulekar, Soumya Basu, Aditya Gopalan, Karthikeyan Shanmugam, Sanjay Shakkottai
• Abstract要約: 線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。 特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。 提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
• 参考スコア（独自算出の注目度）: 51.43660657268171
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a variant of the stochastic linear bandit problem wherein we optimize a linear objective function but rewards are accrued only orthogonal to an unknown subspace (which we interpret as a \textit{protected space}) given only zero-order stochastic oracle access to both the objective itself and protected subspace. In particular, at each round, the learner must choose whether to query the objective or the protected subspace alongside choosing an action. Our algorithm, derived from the OFUL principle, uses some of the queries to get an estimate of the protected space, and (in almost all rounds) plays optimistically with respect to a confidence set for this space. We provide a $\tilde{O}(sd\sqrt{T})$ regret upper bound in the case where the action space is the complete unit ball in $\mathbb{R}^d$, $s < d$ is the dimension of the protected subspace, and $T$ is the time horizon. Moreover, we demonstrate that a discrete action space can lead to linear regret with an optimistic algorithm, reinforcing the sub-optimality of optimism in certain settings. We also show that protection constraints imply that for certain settings, no consistent algorithm can have a regret smaller than $\Omega(T^{3/4}).$ We finally empirically validate our results with synthetic and real datasets.
• Abstract（参考訳）: 我々は、線形目的関数を最適化するが、報酬は未知の部分空間に直交するのみであり(それを \textit{ protecteded space} と解釈する)、目的空間自体と保護された部分空間の両方へのゼロ階確率的オラクルアクセスのみを与える確率的線形包帯問題の変種について研究する。 特に、各ラウンドにおいて、学習者はアクションを選択すると同時に、目的または保護されたサブスペースに問い合わせるかどうかを選択する必要がある。 我々のアルゴリズムはOFULの原理から導かれており、いくつかのクエリを使って保護された空間を推定し、(ほぼすべてのラウンドにおいて)この空間の信頼セットに対して楽観的に再生する。 作用空間が $\mathbb{R}^d$, $s < d$ が保護部分空間の次元であり、$T$ が時間地平線である場合に、$\tilde{O}(sd\sqrt{T})$ 後悔の上界を与える。 さらに, 離散的行動空間は楽観的アルゴリズムによって線形後悔を生じさせ, 特定の設定における楽観主義の下位最適化性を強化することを実証する。 また、保護制約は、一定の設定において、一貫したアルゴリズムが$\Omega(T^{3/4})よりも小さい後悔を持つことができないことを示す。 最終的に私たちは、合成データセットと実際のデータセットで結果を実証的に検証しました。

関連論文リスト

• Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity [3.9657575162895196]
  曖昧な部分空間の埋め込みは、ランダムな$mtimes n$ matrix $Pi$で、その部分空間内のすべてのベクトルのノルムを1pmepsilon$ factorで保存する。 最適次元が $m=Theta(d/epsilon2)$ で、最適間隔が $tilde O (1/epsilon)$ のとき、非零エントリは $Pi$ である。
  論文  参考訳（メタデータ） (2024-11-13T16:58:51Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。 このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
  論文  参考訳（メタデータ） (2023-03-16T15:24:29Z)
• 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)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• High-Dimensional Experimental Design and Kernel Bandits [9.401375475860561]
  最適な線形実験設計の手法を利用して、線形バンディットの最先端の結果を得ています。 G$-optimal designのような目的から返される設計は、実際に潜在的な測定ベクトルのプール上の確率分布である。 我々は、次元 $d$ に対する任意の依存から$n$ を解放する丸め手順を提案する。
  論文  参考訳（メタデータ） (2021-05-12T17:10:56Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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