論文の概要: Testing the Feasibility of Linear Programs with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2406.15648v1
• Date: Fri, 21 Jun 2024 20:56:35 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-25 21:14:22.394512
• Title: Testing the Feasibility of Linear Programs with Bandit Feedback
• Title（参考訳）: 帯域フィードバックを用いた線形プログラムの実現可能性の検証
• Authors: Aditya Gangrade, Aditya Gopalan, Venkatesh Saligrama, Clayton Scott,
• Abstract要約: 我々は,低回帰アルゴリズムと反復対数の漸近法則に基づくテストを開発する。 このテストが信頼できることを証明し、信号レベルに適応する'$Gamma,$ of any instance。 信頼性テストのサンプルコストに対して、最小限の$(Omegad/Gamma2)$で補う。
• 参考スコア（独自算出の注目度）: 53.40256244941895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While the recent literature has seen a surge in the study of constrained bandit problems, all existing methods for these begin by assuming the feasibility of the underlying problem. We initiate the study of testing such feasibility assumptions, and in particular address the problem in the linear bandit setting, thus characterising the costs of feasibility testing for an unknown linear program using bandit feedback. Concretely, we test if $\exists x: Ax \ge 0$ for an unknown $A \in \mathbb{R}^{m \times d}$, by playing a sequence of actions $x_t\in \mathbb{R}^d$, and observing $Ax_t + \mathrm{noise}$ in response. By identifying the hypothesis as determining the sign of the value of a minimax game, we construct a novel test based on low-regret algorithms and a nonasymptotic law of iterated logarithms. We prove that this test is reliable, and adapts to the `signal level,' $\Gamma,$ of any instance, with mean sample costs scaling as $\widetilde{O}(d^2/\Gamma^2)$. We complement this by a minimax lower bound of $\Omega(d/\Gamma^2)$ for sample costs of reliable tests, dominating prior asymptotic lower bounds by capturing the dependence on $d$, and thus elucidating a basic insight missing in the extant literature on such problems.
• Abstract（参考訳）: 最近の文献では、制約付きバンディット問題の研究が急増しているが、これらの既存の方法は全て、根底にある問題の実現可能性を想定して始められている。 本研究では,そのような実現可能性仮定の検証を開始し,特に線形帯域設定における問題に対処し,帯域フィードバックを用いた未知の線形プログラムの実現可能性テストのコストを特徴付ける。 具体的には、$\exists x: Ax \ge 0$ for an unknown $A \in \mathbb{R}^{m \times d}$, by a sequence of action $x_t\in \mathbb{R}^d$, and observed $Ax_t + \mathrm{noise}$ in response。 仮説をミニマックスゲームの値の符号として同定することにより、低回帰アルゴリズムと反復対数の漸近法則に基づく新しいテストを構築する。 このテストは信頼性があり、任意のインスタンスに対して$\Gammaを$\widetilde{O}(d^2/\Gamma^2)$とスケーリングする平均サンプルコストを$\widetilde{O}(d^2/\Gamma^2)$とする。 我々は、信頼テストのサンプルコストに対して$\Omega(d/\Gamma^2)$のミニマックス下限を補完し、$d$への依存を捉えて、先行漸近下限を支配し、既存の文献に欠けている基本的な洞察を解明する。

関連論文リスト

• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Nearly Optimal Algorithms for Level Set Estimation [21.83736847203543]
  線形包帯に対する最近の適応的実験設計手法と関連づけることで, レベルセット推定問題に対する新しいアプローチを提案する。 我々は、我々の境界がほぼ最適であることを示す。すなわち、我々の上限は、しきい値線形帯域に対して既存の下限と一致する。
  論文  参考訳（メタデータ） (2021-11-02T17:45:02Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
  本稿では,リスト復号化可能な線形回帰問題について考察する。 我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
  論文  参考訳（メタデータ） (2021-06-17T17:45:21Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)

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

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