論文の概要: Online Local False Discovery Rate Control: A Resource Allocation
Approach
- arxiv url: http://arxiv.org/abs/2402.11425v1
- Date: Sun, 18 Feb 2024 02:11:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-20 21:24:55.122758
- Title: Online Local False Discovery Rate Control: A Resource Allocation
Approach
- Title(参考訳): オンラインローカル偽発見率制御:資源配分アプローチ
- Authors: Ruicheng Ao, Hongyu Chen, David Simchi-Levi, Feng Zhu
- Abstract要約: 我々は、オンラインリソース割り当て問題として問題を定式化し、決定を受理/退避する。
我々は、小さな対数バッファが$Omega(sqrtT)$または$Omega(T)$から$O(ln2T)$への後悔を減らすのに十分であることを示す。
- 参考スコア(独自算出の注目度): 23.20000810137225
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of online local false discovery rate (FDR) control
where multiple tests are conducted sequentially, with the goal of maximizing
the total expected number of discoveries. We formulate the problem as an online
resource allocation problem with accept/reject decisions, which from a high
level can be viewed as an online knapsack problem, with the additional
uncertainty of random budget replenishment. We start with general arrival
distributions and propose a simple policy that 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 accept arrivals, we
propose a novel policy that incorporates budget buffers. We show that small
additional logarithmic buffers suffice to reduce the regret from
$\Omega(\sqrt{T})$ or even $\Omega(T)$ to $O(\ln^2 T)$. Numerical experiments
are conducted to validate our theoretical findings. Our formulation may have
wider applications beyond the problem considered in this paper, and our results
emphasize how effective policies should be designed to reach a balance between
circumventing wrong accept and reducing wrong reject in online resource
allocation problems with uncertain budgets.
- Abstract(参考訳): オンライン局所的偽発見率(fdr: online local false discovery rate)制御では,複数のテストが順次実施され,期待される発見回数を最大化することが課題である。
本稿では,オンラインの資源配分問題としてこの問題を定式化し,高いレベルからネット上のknapsack問題とみなすことが可能であり,さらにランダムな予算補充の不確実性が生じる。
一般到着分布から始めて、$O(\sqrt{T})$ regret を達成するための簡単なポリシーを提案する。
このような後悔率は一般的には実現不可能であることを示すことで結果を補完する。
その後、焦点を離散的な到着分布に移す。
オンラインリソース割り当て文献における多くの既存の再解決ヒューリスティックは、標準設定における有界損失を達成したとしても、$\Omega(\sqrt{T})$あるいは$\Omega(T)$後悔を引き起こす可能性がある。
標準政策があまりに楽観的になりすぎ、到着を過度に受け入れる傾向があるという観測から、予算バッファーを組み込んだ新しい政策を提案する。
我々は、小さな対数バッファが$\Omega(\sqrt{T})$または$\Omega(T)$から$O(\ln^2T)$への後悔を減らすのに十分であることを示す。
理論的結果を検証するため, 数値実験を行った。
本論文では, 不正な受理の回避と不確実な予算を伴うオンライン資源配分問題における不正な拒否のバランスを保ちつつ, 効果的な政策がいかに設計されるべきかを強調した。
関連論文リスト
- 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 [35.92569763743846]
オフ・ポリティィ・アセスメント」は「オフ・ポリティィ・アセスメント(OPE)」として知られる問題である
我々は、過去の作業で多くの不要な仮定を緩和する、OPE推論のための包括的なフレームワークを提案する。
我々は、OPEの様々な機能に対する信頼シーケンスを導出する。
論文 参考訳(メタデータ) (2022-10-19T17:57:53Z) - A Simple and Optimal Policy Design for Online Learning with Safety
against Heavy-tailed Risk [22.843623578307707]
我々は,古典的多武装バンディット問題における重大リスクに対する安全性を確保する政策を設計する。
この重いリスクは、すべての「インスタンス依存の一貫性」ポリシーに存在します。
予想される後悔と軽微なリスクに対する最悪のケースの最適性は相容れないことを示す。
論文 参考訳(メタデータ) (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) - Curious Explorer: a provable exploration strategy in Policy Learning [0.0]
我々は,新規かつ簡便な状態空間探索戦略であるCurious Explorerを開発した。
Curious Explorerは$rho$から始まり、不訪問状態のセットに割り当てられた固有の報酬を使用することで、一連のポリシーを生成する。
我々は、Curious Explorerが、挑戦的な探索を行い、MDPの性能を向上させることができることを示す。
論文 参考訳(メタデータ) (2021-06-29T15:31:51Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。