論文の概要: Bayesian Online Multiple Testing: A Resource Allocation Approach
- arxiv url: http://arxiv.org/abs/2402.11425v4
- Date: Tue, 16 Jul 2024 01:00:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-17 21:30:11.476707
- Title: Bayesian Online Multiple Testing: A Resource Allocation Approach
- Title(参考訳): Bayesian Online Multiple Testing: リソース割り当てアプローチ
- Authors: Ruicheng Ao, Hongyu Chen, David Simchi-Levi, Feng Zhu,
- Abstract要約: 本研究では,各実験が仮説テストタスクに対応する連続的な実験を行うことの問題点を考察する。
目的は、ローカル・ファルス・ディスカバリー・レート(LFDR)で測定された全ての時点において、低いエラー率を維持しながら発見回数を最大化することである。
予算安全バッファを組み込んだ新しいポリシーを提案する。
- 参考スコア(独自算出の注目度): 21.23710184381363
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of sequentially conducting multiple experiments where each experiment corresponds to a hypothesis testing task. At each time point, the experimenter must make an irrevocable decision of whether to reject the null hypothesis (or equivalently claim a discovery) before the next experimental result arrives. The goal is to maximize the number of discoveries while maintaining a low error rate at all time points measured by Local False Discovery Rate (LFDR). We formulate the problem as an online knapsack problem with exogenous random budget replenishment. We start with general arrival distributions and show that a simple policy achieves a $O(\sqrt{T})$ regret. We complement the result by showing that such regret rate is in general not improvable. We then shift our focus to discrete arrival distributions. We find that many existing re-solving heuristics in the online resource allocation literature, albeit achieve bounded loss in canonical settings, may incur a $\Omega(\sqrt{T})$ or even a $\Omega(T)$ regret. With the observation that canonical policies tend to be too optimistic and over claim discoveries, we propose a novel policy that incorporates budget safety buffers. It turns out that a little more safety can greatly enhance efficiency -- small additional logarithmic buffers suffice to reduce the regret from $\Omega(\sqrt{T})$ or even $\Omega(T)$ to $O(\ln^2 T)$. From a practical perspective, we extend the policy to the scenario with continuous arrival distributions, time-dependent information structures, as well as unknown $T$. We conduct both synthetic experiments and empirical applications on a time series data from New York City taxi passengers to validate the performance of our proposed policies. Our results emphasize how effective policies should be designed in online resource allocation problems with exogenous budget replenishment.
- Abstract(参考訳): 各実験が仮説テストタスクに対応する複数の実験を順次実施する問題を考察する。
各時点において、実験者は、次の実験結果が到着する前に、ヌル仮説を拒絶するか(または、同等に発見を主張するか)という不可解な決定をしなければならない。
目標は、ローカル偽発見率(LFDR)によって測定されるすべての時点において、低いエラー率を維持しながら、発見回数を最大化することである。
オンラインのknapsack問題として,外因性ランダム予算補充問題として定式化する。
まず、一般的な到着分布から始め、単純なポリシーが$O(\sqrt{T})$後悔を達成することを示す。
このような後悔率は一般的には実現不可能であることを示すことで、結果を補完する。
次に、個別の到着分布に焦点を移します。
オンラインリソース割り当て文献における多くの既存の再解決ヒューリスティックは、標準設定における有界損失を達成したとしても、$\Omega(\sqrt{T})$あるいは$\Omega(T)$後悔を招きかねない。
標準政策は楽観的すぎる傾向にあり,要求発見を超越する傾向にあることから,予算安全バッファを組み込んだ新たな政策を提案する。
小さな対数バッファは、後悔を$\Omega(\sqrt{T})$または$\Omega(T)$から$O(\ln^2T)$に減らすのに十分である。
実用の観点からは、ポリシーを連続到着分布、時間依存情報構造、未知の$T$のシナリオに拡張する。
ニューヨーク市のタクシー乗客の時系列データに合成実験と経験的応用の両方を施し,提案手法の有効性を検証した。
本研究は,外因性予算補充を伴うオンライン資源配分問題において,政策がいかに効果的に設計されるべきかを強調した。
関連論文リスト
- Oracle-Efficient Reinforcement Learning for Max Value Ensembles [7.404901768256101]
大または無限の状態空間における強化学習(RL)は、理論上、実験的に困難である。
この作業では、$textitmax-following Policy$と競合することを目指しています。
我々の主な成果は、構成ポリシーのみにアクセスすると、最大フォローポリシーと競合する効率的なアルゴリズムである。
論文 参考訳(メタデータ) (2024-05-27T01:08:23Z) - Online Policy Learning and Inference by Matrix Completion [12.527541242185404]
行列完備帯域(MCB)として問題を定式化する。
我々は、$epsilon$-greedy banditとオンライン勾配降下について検討する。
より早く崩壊する探索は、より少ない後悔をもたらすが、最適なポリシーをより正確に学習する。
論文 参考訳(メタデータ) (2024-04-26T13:19:27Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳(メタデータ) (2023-10-01T01:37:02Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-19T01:09:24Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳(メタデータ) (2023-01-31T03:49:00Z) - Anytime-valid off-policy inference for contextual bandits [34.721189269616175]
コンテキストバンディットアルゴリズムは、観測されたコンテキストを$X_t$からアクションにマッピングする。
データの収集に使われたロギングポリシーと異なる仮説的ポリシーの特性を推定することは、しばしば関心がある。
我々は、過去の作業で不要な条件を緩和するOPE推論のための包括的なフレームワークを提案する。
論文 参考訳(メタデータ) (2022-10-19T17:57:53Z) - A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits [27.058087400790555]
マルチアームバンディット問題について検討し,期待された後悔に対する最悪のケース最適性と,後悔の分布に対する軽微なリスクの両方を享受する新しいポリシーを設計する。
経営的な観点から、我々の新しい政策設計は、より良い尾の分布をもたらし、祝福された政策よりも好まれることがわかった。
論文 参考訳(メタデータ) (2022-06-07T02:10:30Z) - Doubly Robust Distributionally Robust Off-Policy Evaluation and Learning [59.02006924867438]
オフ政治評価と学習(OPE/L)は、オフラインの観察データを使用してより良い意思決定を行う。
近年の研究では、分散ロバストなOPE/L (DROPE/L) が提案されているが、この提案は逆正則重み付けに依存している。
KL分散不確実性集合を用いたDROPE/Lの最初のDRアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-19T20:00:44Z) - Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。
複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
論文 参考訳(メタデータ) (2020-10-21T13:43:48Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Differentiable Bandit Exploration [38.81737411000074]
我々は、$mathcalP$からサンプルを使って未知のディストリビューション$mathcalP$についてそのようなポリシーを学ぶ。
我々のアプローチはメタラーニングの形式であり、その形式について強い仮定をすることなく$mathcalP$のプロパティを利用する。
論文 参考訳(メタデータ) (2020-02-17T05:07:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。