論文の概要: Pure Exploration in Bandits with Linear Constraints
- arxiv url: http://arxiv.org/abs/2306.12774v1
- Date: Thu, 22 Jun 2023 10:00:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-23 14:57:09.382220
- Title: Pure Exploration in Bandits with Linear Constraints
- Title（参考訳）: 線形制約をもつバンディットの純粋探査
- Authors: Emil Carlsson, Debabrota Basu, Fredrik D. Johansson, Devdatt Dubhashi
- Abstract要約: マルチアーム・バンディット・セットアップにおいて、最適ポリシーを一定の信頼度で識別する問題に対処する。
この設定に最適な2つのアルゴリズムを導入する。1つはトラック・アンド・ストップ法であり、もう1つはゲーム理論に基づく手法である。
限界を検証し、制約が問題の硬さをどのように変えるかを視覚化する実験結果を提供する。
- 参考スコア（独自算出の注目度）: 11.448769367291929
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We address the problem of identifying the optimal policy with a fixed
confidence level in a multi-armed bandit setup, when \emph{the arms are subject
to linear constraints}. Unlike the standard best-arm identification problem
which is well studied, the optimal policy in this case may not be deterministic
and could mix between several arms. This changes the geometry of the problem
which we characterize via an information-theoretic lower bound. We introduce
two asymptotically optimal algorithms for this setting, one based on the
Track-and-Stop method and the other based on a game-theoretic approach. Both
these algorithms try to track an optimal allocation based on the lower bound
and computed by a weighted projection onto the boundary of a normal cone.
Finally, we provide empirical results that validate our bounds and visualize
how constraints change the hardness of the problem.
- Abstract（参考訳）: 我々は,多腕バンディット設定における最適ポリシーを一定の信頼度で識別する問題に, 'emph{the arms' が線形制約を受ける際に対処する。
良く研究されている標準的な最良の腕識別問題とは異なり、この場合の最適方針は決定論的ではなく、複数の腕の間で混合することができる。
これは、情報理論の下界によって特徴づけられる問題の幾何学を変える。
本稿では,この設定に対して,トラック・アンド・ストップ法とゲーム理論に基づく2つの漸近的最適アルゴリズムを提案する。
これらのアルゴリズムは、下界に基づいて最適な割り当てを追跡し、通常の円錐の境界への重み付き投影によって計算する。
最後に,限界を検証し,制約が問題の硬さを変える様子を可視化する実験結果を提供する。
関連論文リスト
- Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。
まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。
第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
論文 参考訳（メタデータ） (2024-10-24T15:26:14Z) - Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。
本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。
2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文 参考訳（メタデータ） (2024-09-24T04:39:47Z) - Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。
私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
論文 参考訳（メタデータ） (2024-05-25T08:09:36Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳（メタデータ） (2020-06-29T14:25:51Z) - Best Arm Identification in Spectral Bandits [0.0]
BAI(Best Arm Identification)は、パラメータチューニングから臨床試験まで、多くの応用において重要な課題である。
グラフの滑らか度制約を伴う帯域モデルにおいて,信頼度を固定したベストアーム識別について検討する。
論文 参考訳（メタデータ） (2020-05-20T04:12:04Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳（メタデータ） (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。