論文の概要: Online Learning of Optimal Sequential Testing Policies

• arxiv url: http://arxiv.org/abs/2509.03707v1
• Date: Wed, 03 Sep 2025 20:44:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-05 20:21:09.968457
• Title: Online Learning of Optimal Sequential Testing Policies
• Title（参考訳）: 最適シーケンステストのオンライン学習
• Authors: Qiyuan Chen, Raed Al Kontar,
• Abstract要約: 被験者のストリームに対して最適なテストポリシーを求めるオンライン学習問題について検討する。 対象に対するすべての候補テストを実行することで、より多くの情報が得られるが、サブセットのみを選択することが望ましい場合が多い。 我々は、ミニマックスの後悔は少なくとも$Omega(Tfrac23)$としてスケールしなければならないことを証明し、エピソードMDPの$Theta(sqrtT)$レートとは対照的である。
• 参考スコア（独自算出の注目度）: 7.8024154978341365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies an online learning problem that seeks optimal testing policies for a stream of subjects, each of whom can be evaluated through a sequence of candidate tests drawn from a common pool. We refer to this problem as the Online Testing Problem (OTP). Although conducting every candidate test for a subject provides more information, it is often preferable to select only a subset when tests are correlated and costly, and make decisions with partial information. If the joint distribution of test outcomes were known, the problem could be cast as a Markov Decision Process (MDP) and solved exactly. In practice, this distribution is unknown and must be learned online as subjects are tested. When a subject is not fully tested, the resulting missing data can bias estimates, making the problem fundamentally harder than standard episodic MDPs. We prove that the minimax regret must scale at least as $\Omega(T^{\frac{2}{3}})$, in contrast to the $\Theta(\sqrt{T})$ rate in episodic MDPs, revealing the difficulty introduced by missingness. This elevated lower bound is then matched by an Explore-Then-Commit algorithm whose cumulative regret is $\tilde{O}(T^{\frac{2}{3}})$ for both discrete and Gaussian distributions. To highlight the consequence of missingness-dependent rewards in OTP, we study a variant called the Online Cost-sensitive Maximum Entropy Sampling Problem, where rewards are independent of missing data. This structure enables an iterative-elimination algorithm that achieves $\tilde{O}(\sqrt{T})$ regret, breaking the $\Omega(T^{\frac{2}{3}})$ lower bound for OTP. Numerical results confirm our theory in both settings. Overall, this work deepens the understanding of the exploration--exploitation trade-off under missing data and guides the design of efficient sequential testing policies.
• Abstract（参考訳）: 本稿では,複数の被験者に対して最適なテストポリシーを求めるオンライン学習問題について検討し,それぞれが共通のプールから抽出された候補テストのシーケンスを通じて評価できることを示した。 この問題をオンラインテスト問題(OTP)と呼ぶ。 被験者に対してすべての候補テストを実行することでより多くの情報が得られるが、テストが相関してコストがかかる場合にのみサブセットを選択し、部分的な情報で決定することが望ましい。 テスト結果の連立分布が分かっていれば、問題はマルコフ決定過程(MDP)としてキャストされ、正確に解かれる。 実際には、この分布は未知であり、被験者がテストされる際にはオンラインで学ぶ必要がある。 被験者が完全にテストされていない場合、結果として得られたデータに偏りが生じるため、問題は標準のエピソードMDPよりも根本的に難しい。 我々は、ミニマックスの後悔は少なくとも$\Omega(T^{\frac{2}{3}})$としてスケールしなければならないことを証明している。 この高次の下界は、離散分布とガウス分布の両方に対して、累積後悔が$\tilde{O}(T^{\frac{2}{3}})$であるエクスプローラー・Then-Commitアルゴリズムで一致する。 OTPにおける損失依存報酬の結果を明らかにするため,オンラインコスト感性最大エントロピーサンプリング問題(Online Cost-sensitive Maximum Entropy Sampling Problem)と呼ばれる変種について検討した。 この構造により、反復消去アルゴリズムが$\tilde{O}(\sqrt{T})$ regretを達成し、OTPの$\Omega(T^{\frac{2}{3}})$ lower boundを破ることができる。 数値的な結果から,両設定で理論が立証される。 全体として、この研究は、欠落したデータの下での探索-爆発的トレードオフの理解を深め、効率的なシーケンシャルなテストポリシーの設計を導く。

関連論文リスト

• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
  条件分布は機械学習の中心的な問題です ペアデータとペアデータの両方を統合する新しいパラダイムを提案する。 提案手法は任意の誤差で理論上真の条件分布を復元可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-03T16:12:59Z)
• Bayesian Online Multiple Testing: A Resource Allocation Approach [21.23710184381363]
  本研究では,各実験が仮説テストタスクに対応する連続的な実験を行うことの問題点を考察する。 目的は、ローカル・ファルス・ディスカバリー・レート(LFDR)で測定された全ての時点において、低いエラー率を維持しながら発見回数を最大化することである。 予算安全バッファを組み込んだ新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2024-02-18T02:11:54Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。 グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。 提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
  論文  参考訳（メタデータ） (2024-02-08T14:43:56Z)
• Active Cost-aware Labeling of Streaming Data [11.501619634838312]
  本研究では,アクティブな学習者がデータポイントのストリームに直面するストリーミングデータのラベル付けについて検討する。 まず、データ入力が$K$の離散分布の1つに属し、ラベリングコストと予測誤差をキャプチャする損失によってこの問題を定式化する際の設定について検討する。 ラベル付けコストが$B$の場合、不確実性が時間とコスト依存しきい値よりも大きい場合のラベル付けを選択するアルゴリズムは、最悪の$widetildeO(Bfrac1)上限を達成する。
  論文  参考訳（メタデータ） (2023-04-13T20:23:27Z)
• Sequential Kernelized Independence Testing [77.237958592189]
  我々は、カーネル化依存度にインスパイアされたシーケンシャルなカーネル化独立試験を設計する。 シミュレーションデータと実データの両方にアプローチのパワーを実証する。
  論文  参考訳（メタデータ） (2022-12-14T18:08:42Z)

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

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