論文の概要: Approximation Algorithms for Active Sequential Hypothesis Testing

• arxiv url: http://arxiv.org/abs/2103.04250v1
• Date: Sun, 7 Mar 2021 03:49:19 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-09 15:57:39.137825
• Title: Approximation Algorithms for Active Sequential Hypothesis Testing
• Title（参考訳）: アクティブシーケンシャル仮説テストのための近似アルゴリズム
• Authors: Kyra Gan, Su Jia, Andrew Li
• Abstract要約: 本稿では,アクティブシーケンシャル仮説テストのための最初の近似アルゴリズムを提案する。 アルゴリズムの性能を合成データと実データの両方を用いて数値的に調査し,アルゴリズムが提案した方針を上回っていることを示した。
• 参考スコア（独自算出の注目度）: 3.840659854046464
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the problem of active sequential hypotheses testing (ASHT), a learner seeks to identify the true hypothesis $h^*$ from among a set of hypotheses $H$. The learner is given a set of actions and knows the outcome distribution of any action under any true hypothesis. While repeatedly playing the entire set of actions suffices to identify $h^*$, a cost is incurred with each action. Thus, given a target error $\delta>0$, the goal is to find the minimal cost policy for sequentially selecting actions that identify $h^*$ with probability at least $1 - \delta$. This paper provides the first approximation algorithms for ASHT, under two types of adaptivity. First, a policy is partially adaptive if it fixes a sequence of actions in advance and adaptively decides when to terminate and what hypothesis to return. Under partial adaptivity, we provide an $O\big(s^{-1}(1+\log_{1/\delta}|H|)\log (s^{-1}|H| \log |H|)\big)$-approximation algorithm, where $s$ is a natural separation parameter between the hypotheses. Second, a policy is fully adaptive if action selection is allowed to depend on previous outcomes. Under full adaptivity, we provide an $O(s^{-1}\log (|H|/\delta)\log |H|)$-approximation algorithm. We numerically investigate the performance of our algorithms using both synthetic and real-world data, showing that our algorithms outperform a previously proposed heuristic policy.
• Abstract（参考訳）: アクティブ・シーケンシャル仮説テスト(英語版)(asht)の問題において、学習者は、一連の仮説のうち、真の仮説である$h^*$を同定しようとする。 学習者は一連の行動を与えられ、任意の真の仮説の下での行動の結果分布を知る。 アクションの集合全体を繰り返し再生すると、$h^*$を識別するのに十分だが、アクションごとにコストがかかる。 したがって、ターゲットエラー $\delta>0$ が与えられた場合、少なくとも1 - \delta$ の確率で $h^*$ を識別するアクションを逐次選択するための最小コストポリシーを見つけることが目的である。 本稿では2種類の適応性の下でASHTの最初の近似アルゴリズムを提供する。 まず、ポリシーが事前に一連のアクションを修正し、いつ終了し、どの仮説を返すかを適応的に決定すれば、部分的に適応する。 部分的適応性の下では、$o\big(s^{-1}(1+\log_{1/\delta}|h|)\log (s^{-1}|h| \log |h|)\big)$近似アルゴリズムを提供する。 第二に、アクションの選択が以前の結果に依存している場合、ポリシーは完全に適応的です。 完全な適応性の下で、$O(s^{-1}\log (|H|/\delta)\log |H|)$-近似アルゴリズムを提供する。 合成データと実世界のデータの両方を用いて,アルゴリズムの性能を数値的に検討し,提案したヒューリスティック・ポリシーよりも優れていることを示す。

関連論文リスト

• A Competitive Algorithm for Agnostic Active Learning [5.4579367210379335]
  アクティブな学習のための最も一般的なアルゴリズムは、不一致係数と呼ばれるパラメータでその性能を表現する。 我々は、任意の二進仮説クラス$H$と分布$D_X$ over$X$に対して最適なアルゴリズムと競合するアルゴリズムを得る。 我々のアルゴリズムの$O(log |H|)$オーバーヘッドよりは、NPハードである。
  論文  参考訳（メタデータ） (2023-10-28T19:01:16Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Minimum Cost Adaptive Submodular Cover [4.680686256929023]
  適応部分モジュラ函数の最小コスト被覆の問題を考える。 このアルゴリズムは,すべての$pge 1$に対して,同時に$(p+1)p+1cdot (ln Q+1)p$近似を保証することを示す。
  論文  参考訳（メタデータ） (2022-08-17T15:26:47Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation [2.294014185517203]
  本稿では、収束理論を準確率近似に拡張することを目的とする。 強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
  論文  参考訳（メタデータ） (2020-09-30T04:44:45Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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