論文の概要: 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)$への後悔を減らすのに十分であることを示す。
理論的結果を検証するため, 数値実験を行った。
本論文では, 不正な受理の回避と不確実な予算を伴うオンライン資源配分問題における不正な拒否のバランスを保ちつつ, 効果的な政策がいかに設計されるべきかを強調した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。