論文の概要: 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を破ることができる。 数値的な結果から,両設定で理論が立証される。 全体として、この研究は、欠落したデータの下での探索-爆発的トレードオフの理解を深め、効率的なシーケンシャルなテストポリシーの設計を導く。

関連論文リスト

• Online Learning with Probing for Sequential User-Centric Selection [8.45399786458738]
  そこで,学習者がまず武器のサブセットを探索して資源や報酬の副次情報を取得し,その後に$K$プレイを$M$アームに割り当てる。 既知の分布を持つオフライン設定に対しては、定数係数近似により $zeta = (e-1)/ (2e-1)$ が保証される。 未知の分布を持つオンライン・セッティングについては、OLPA(Bandit algorithm)を紹介します。
  論文  参考訳（メタデータ） (2025-07-27T03:32:51Z)
• On Traceability in $\ell_p$ Stochastic Convex Optimization [34.23960368886818]
  学習アルゴリズムが$m$-traceableであるとは、そのアウトプットを分析することで、トレーニングサンプルの少なくとも$m$を識別できるということである。 我々の主な成果は、SCOにおけるトレーサビリティと過剰リスクの根本的なトレードオフを明らかにすることである。
  論文  参考訳（メタデータ） (2025-02-24T18:10:06Z)
• 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)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Active Cost-aware Labeling of Streaming Data [11.501619634838312]
  本研究では,アクティブな学習者がデータポイントのストリームに直面するストリーミングデータのラベル付けについて検討する。 まず、データ入力が$K$の離散分布の1つに属し、ラベリングコストと予測誤差をキャプチャする損失によってこの問題を定式化する際の設定について検討する。 ラベル付けコストが$B$の場合、不確実性が時間とコスト依存しきい値よりも大きい場合のラベル付けを選択するアルゴリズムは、最悪の$widetildeO(Bfrac1)上限を達成する。
  論文  参考訳（メタデータ） (2023-04-13T20:23:27Z)
• Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning [3.222802562733787]
  トレーニング環境とテスト環境のパラメータミスマッチに対して頑健な制御ポリシーを学習することの問題点を考察する。 本研究では,4つの異なる発散によって特定される不確実性集合に対して,ロバスト位相値学習(RPVL)アルゴリズムを提案する。 提案アルゴリズムは,既存の結果より一様によいサンプル複雑性を$tildemathcalO(|mathcalSmathcalA| H5)$とする。
  論文  参考訳（メタデータ） (2023-03-05T21:47:08Z)
• Sequential Kernelized Independence Testing [77.237958592189]
  我々は、カーネル化依存度にインスパイアされたシーケンシャルなカーネル化独立試験を設計する。 シミュレーションデータと実データの両方にアプローチのパワーを実証する。
  論文  参考訳（メタデータ） (2022-12-14T18:08:42Z)
• 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)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)

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

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