論文の概要: Restless Linear Bandits

• arxiv url: http://arxiv.org/abs/2405.10817v1
• Date: Fri, 17 May 2024 14:37:39 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-20 15:53:32.540707
• Title: Restless Linear Bandits
• Title（参考訳）: レスト・リニアバンド
• Authors: Azadeh Khaleghi,
• Abstract要約: 未知の$mathbbRd$-valued stationary $varphi$-mixing sequence of parameters $(theta_t,t in mathbbN)$ が存在すると仮定される。 指数混合率が$theta_t$の場合、LinMix-UCBと呼ばれる楽観的なアルゴリズムが提案される。
• 参考スコア（独自算出の注目度）: 5.00389879175348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A more general formulation of the linear bandit problem is considered to allow for dependencies over time. Specifically, it is assumed that there exists an unknown $\mathbb{R}^d$-valued stationary $\varphi$-mixing sequence of parameters $(\theta_t,~t \in \mathbb{N})$ which gives rise to pay-offs. This instance of the problem can be viewed as a generalization of both the classical linear bandits with iid noise, and the finite-armed restless bandits. In light of the well-known computational hardness of optimal policies for restless bandits, an approximation is proposed whose error is shown to be controlled by the $\varphi$-dependence between consecutive $\theta_t$. An optimistic algorithm, called LinMix-UCB, is proposed for the case where $\theta_t$ has an exponential mixing rate. The proposed algorithm is shown to incur a sub-linear regret of $\mathcal{O}\left(\sqrt{d n\mathrm{polylog}(n) }\right)$ with respect to an oracle that always plays a multiple of $\mathbb{E}\theta_t$. The main challenge in this setting is to ensure that the exploration-exploitation strategy is robust against long-range dependencies. The proposed method relies on Berbee's coupling lemma to carefully select near-independent samples and construct confidence ellipsoids around empirical estimates of $\mathbb{E}\theta_t$.
• Abstract（参考訳）: 線形帯域問題のより一般的な定式化は、時間とともに依存を許容すると考えられる。 具体的には、未知の$\mathbb{R}^d$-valued stationary $\varphi$-mixing sequence of parameters $(\theta_t,~t \in \mathbb{N})$ が存在すると仮定される。 この問題の例は、イドノイズを持つ古典的線形包帯の一般化と、有限武装のレスレス包帯の一般化と見なすことができる。 レスレスバンディットに対する最適ポリシーのよく知られた計算困難さを考慮して、連続する$\theta_t$間の$\varphi$-dependenceによって誤差を制御する近似が提案される。 LinMix-UCBと呼ばれる楽観的なアルゴリズムは、$\theta_t$が指数混合率を持つ場合に提案される。 提案アルゴリズムは、常に$\mathbb{E}\theta_t$の倍数のオラクルに対して、$\mathcal{O}\left(\sqrt{d n\mathrm{polylog}(n) }\right)$のサブ線形後悔を引き起こすことを示す。 この設定の主な課題は、探査・探査戦略が長距離依存に対して堅牢であることを保証することである。 提案手法はベルビーのカップリング補題に頼り、ほぼ独立な標本を慎重に選択し、$\mathbb{E}\theta_t$の実験的推定値の周りの信頼楕円体を構築する。

関連論文リスト

• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation [22.51165277694864]
  本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。 LSAは$d$次元線形系の近似解を計算するために用いられる。
  論文  参考訳（メタデータ） (2022-07-10T14:36:04Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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