論文の概要: A Reduction Algorithm for Markovian Contextual Linear Bandits

• arxiv url: http://arxiv.org/abs/2603.12530v1
• Date: Fri, 13 Mar 2026 00:12:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-16 17:38:11.819085
• Title: A Reduction Algorithm for Markovian Contextual Linear Bandits
• Title（参考訳）: マルコフ文脈線形帯域の削減アルゴリズム
• Authors: Kaan Buyukkalayci, Osama Hanna, Christina Fragouli,
• Abstract要約: 最近の研究は、文脈が描画されるとき、すなわち、線形文脈の帯域幅を単一コンテキストの線形帯域幅に減らすことができることを示している。 時間的に相関した可観測性を持つアプリケーションによって動機付けられ、この視点をマルコフの文脈的線形帯域に拡張する。
• 参考スコア（独自算出の注目度）: 8.172698632831885
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work shows that when contexts are drawn i.i.d., linear contextual bandits can be reduced to single-context linear bandits. This ``contexts are cheap" perspective is highly advantageous, as it allows for sharper finite-time analyses and leverages mature techniques from the linear bandit literature, such as those for misspecification and adversarial corruption. Motivated by applications with temporally correlated availability, we extend this perspective to Markovian contextual linear bandits, where the action set evolves via an exogenous Markov chain. Our main contribution is a reduction that applies under uniform geometric ergodicity. We construct a stationary surrogate action set to solve the problem using a standard linear bandit oracle, employing a delayed-update scheme to control the bias induced by the nonstationary conditional context distributions. We further provide a phased algorithm for unknown transition distributions that learns the surrogate mapping online. In both settings, we obtain a high-probability worst-case regret bound matching that of the underlying linear bandit oracle, with only lower-order dependence on the mixing time.
• Abstract（参考訳）: 最近の研究は、文脈が描画されるとき、すなわち、線形文脈の帯域幅を単一コンテキストの線形帯域幅に減らすことができることを示している。 この『contexts are cheap』の観点は非常に有利であり、それはよりシャープな有限時間解析を可能にし、不特定性や敵対的腐敗などの線形バンディット文学からの成熟した技術を活用する。 時間的に相関した可観測性を持つ応用によって動機付けられ、この視点をマルコフの文脈的線形帯域へと拡張し、そこでは作用集合は外生的マルコフ連鎖を介して進化する。 我々の主な貢献は、均一な幾何学的エルゴード性の下で適用される還元である。 本研究では,非定常条件付き文脈分布によって生じるバイアスを制御するために,遅延更新方式を用いて,標準線形バンディットオラクルを用いてこの問題を解決するための定常サロゲート動作セットを構築した。 さらに、オンライン上で代理写像を学習する未知の遷移分布に対する位相付きアルゴリズムを提供する。 いずれの設定においても, 混合時間にのみ低次依存しか持たず, 基礎となる線形バンディットオラクルと一致した, 確率の高い最悪ケースの残差が得られている。

関連論文リスト

• On the Optimal Regret of Locally Private Linear Contextual Bandit [18.300225068036642]
  局所的なプライベートな文脈的帯域に対して,$tilde O(sqrtT)$ regret upper bound を達成可能であることを示す。 我々の解決策は、いくつかの新しいアルゴリズム的および分析的アイデアに依存している。
  論文  参考訳（メタデータ） (2024-04-15T02:00:24Z)
• Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms [39.70492757288025]
  我々は,意思決定者がコンテキストを提供するコンテキスト線形帯域問題に対処する。 文脈問題を線形バンディット問題として解くことができることを示す。 この結果から,文脈的線形包帯に対して$O(dsqrtTlog T)$高確率残差が生じることが示唆された。
  論文  参考訳（メタデータ） (2022-11-08T22:18:53Z)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。 我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。 推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
  論文  参考訳（メタデータ） (2022-10-18T16:11:55Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。 ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。 本稿では,FTRLに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-28T08:25:26Z)
• When Are Linear Stochastic Bandits Attackable? [47.25702824488642]
  本稿では,$k$のリニアバンディット環境の攻撃性について検討する。 本稿では,LinUCBとロバスト位相除去に対する2段階攻撃法を提案する。
  論文  参考訳（メタデータ） (2021-10-18T04:12:09Z)
• Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
  ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。 情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。 これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2021-05-25T10:08:41Z)
• Parallelizing Contextual Linear Bandits [82.65675585004448]
  並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。 また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
  論文  参考訳（メタデータ） (2021-05-21T22:22:02Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Recurrent Neural-Linear Posterior Sampling for Nonstationary Contextual Bandits [9.877980800275507]
  本稿では,エージェントと環境間のインタラクションの生履歴のみに基づいて,意思決定の関連状況を表現する手法を提案する。 このアプローチは、リカレントニューラルネットワークによって抽出された特徴と、後続サンプリングに基づく文脈線形帯域アルゴリズムの組み合わせに依存する。
  論文  参考訳（メタデータ） (2020-07-09T12:46:51Z)

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

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