論文の概要: Combinatorial Semi-Bandit in the Non-Stationary Environment

• arxiv url: http://arxiv.org/abs/2002.03580v2
• Date: Sat, 19 Jun 2021 06:27:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-02 08:17:51.905393
• Title: Combinatorial Semi-Bandit in the Non-Stationary Environment
• Title（参考訳）: 非定常環境における組合せセミバンド
• Authors: Wei Chen, Liwei Wang, Haoyu Zhao, Kai Zheng
• Abstract要約: スイッチングケースと動的ケースの両方において,非定常半帯域問題について検討する。 別の手法を用いることで、我々のアルゴリズムは $mathcal S$ あるいは $mathcal V$ のパラメータをもはや知る必要がなくなるが、後悔する境界は準最適になる可能性がある。
• 参考スコア（独自算出の注目度）: 27.394284055156795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate the non-stationary combinatorial semi-bandit problem, both in the switching case and in the dynamic case. In the general case where (a) the reward function is non-linear, (b) arms may be probabilistically triggered, and (c) only approximate offline oracle exists \cite{wang2017improving}, our algorithm achieves $\tilde{\mathcal{O}}(\sqrt{\mathcal{S} T})$ distribution-dependent regret in the switching case, and $\tilde{\mathcal{O}}(\mathcal{V}^{1/3}T^{2/3})$ in the dynamic case, where $\mathcal S$ is the number of switchings and $\mathcal V$ is the sum of the total ``distribution changes''. The regret bounds in both scenarios are nearly optimal, but our algorithm needs to know the parameter $\mathcal S$ or $\mathcal V$ in advance. We further show that by employing another technique, our algorithm no longer needs to know the parameters $\mathcal S$ or $\mathcal V$ but the regret bounds could become suboptimal. In a special case where the reward function is linear and we have an exact oracle, we design a parameter-free algorithm that achieves nearly optimal regret both in the switching case and in the dynamic case without knowing the parameters in advance.
• Abstract（参考訳）: 本稿では,スイッチングケースと動的ケースの両方において,非定常組合せ半帯域問題について検討する。 一般的なケースでは (a)報酬関数は非線形である。 b) 腕が確率的に引き起こされる場合,及び (c) 近似的なオフラインオラクルのみが存在し、我々のアルゴリズムは、スイッチングケースにおける分布依存の後悔を$\tilde{\mathcal{O}}(\sqrt{\mathcal{S} T})$と、動的ケースでは$\tilde{\mathcal{O}}(\mathcal{V}^{1/3}T^{2/3})$を達成する。 両方のシナリオにおける後悔境界はほぼ最適であるが、我々のアルゴリズムは事前に$\mathcal S$または$\mathcal V$を知る必要がある。 さらに、他の手法を用いることで、我々のアルゴリズムはパラメータ $\mathcal S$ あるいは $\mathcal V$ を知る必要がなくなるが、後悔する境界は最適でないことを示す。 報酬関数が線形で正確なオラクルを持つ特殊な場合、スイッチングケースと動的ケースの両方において、パラメータを事前に知ることなくほぼ最適に後悔するパラメータフリーアルゴリズムを設計する。

関連論文リスト

• Partially Unitary Learning [0.0]
  ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。 この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-16T17:13:55Z)
• Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes [23.94542304111204]
  勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。 規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
  論文  参考訳（メタデータ） (2023-06-16T17:00:51Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• 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)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Dimension Reduction in Contextual Online Learning via Nonparametric Variable Selection [8.250528027387196]
  文献によれば、最適の後悔は$tildeO(T(d_x*+d_y+1)/(d_x*+d_y+2))$である。 我々は,非パラメトリックな設定にLASSOを適用するために,ビンニングや投票などの新しいアイデアを取り入れたtextitBV-LASSO という変数選択アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-17T13:08:45Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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