論文の概要: Non-Stationary Online Resource Allocation: Learning from a Single Sample
- arxiv url: http://arxiv.org/abs/2602.18114v1
- Date: Fri, 20 Feb 2026 10:07:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-23 18:01:41.291371
- Title: Non-Stationary Online Resource Allocation: Learning from a Single Sample
- Title（参考訳）: 非定常オンラインリソース割り当て:単一サンプルから学ぶ
- Authors: Yiding Feng, Jiashuo Jiang, Yige Wang,
- Abstract要約: 最低限のオフラインデータ要求で,非定常要求下でのオンラインリソース割り当てについて検討する。
本稿では,この問題をモジュラーコンポーネントに分解する,型依存型量子型メタ政治を提案する。
- 参考スコア（独自算出の注目度）: 5.81028169940199
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study online resource allocation under non-stationary demand with a minimum offline data requirement. In this problem, a decision-maker must allocate multiple types of resources to sequentially arriving queries over a finite horizon. Each query belongs to a finite set of types with fixed resource consumption and a stochastic reward drawn from an unknown, type-specific distribution. Critically, the environment exhibits arbitrary non-stationarity -- arrival distributions may shift unpredictably-while the algorithm requires only one historical sample per period to operate effectively. We distinguish two settings based on sample informativeness: (i) reward-observed samples containing both query type and reward realization, and (ii) the more challenging type-only samples revealing only query type information. We propose a novel type-dependent quantile-based meta-policy that decouples the problem into modular components: reward distribution estimation, optimization of target service probabilities via fluid relaxation, and real-time decisions through dynamic acceptance thresholds. For reward-observed samples, our static threshold policy achieves $\tilde{O}(\sqrt{T})$ regret. For type-only samples, we first establish that sublinear regret is impossible without additional structure; under a mild minimum-arrival-probability assumption, we design both a partially adaptive policy attaining the same $\tilde{O}({T})$ bound and, more significantly, a fully adaptive resolving policy with careful rounding that achieves the first poly-logarithmic regret guarantee of $O((\log T)^3)$ for non-stationary multi-resource allocation. Our framework advances prior work by operating with minimal offline data (one sample per period), handling arbitrary non-stationarity without variation-budget assumptions, and supporting multiple resource constraints.
- Abstract（参考訳）: 最低限のオフラインデータ要求で,非定常要求下でのオンラインリソース割り当てについて検討する。
この問題では、意思決定者は、有限の地平線上で逐次到着するクエリに複数のタイプのリソースを割り当てなければならない。
各クエリは、固定リソース消費と未知の型固有の分布から引き出された確率的な報酬を持つ有限型のタイプに属します。
決定的に、環境は任意の非定常性を示し、到着分布は予測不可能に変化する可能性がある。
サンプル情報量に基づく2つの設定を区別する。
(i)クエリタイプと報酬実現の両方を含む報酬保存サンプル、及び
(ii)クエリタイプ情報のみを明らかにする、より困難な型のみのサンプル。
本稿では,この問題をモジュラーコンポーネントに分解する新しいタイプ依存量子型メタポリシクスを提案する。
報酬が守られたサンプルに対して、我々の静的しきい値ポリシーは $\tilde{O}(\sqrt{T})$ regret を達成する。
最小値の最小値確率仮定の下では、同じ$\tilde{O}({T})$バウンドを満たす部分適応ポリシーと、より顕著なことに、最小値のマルチリソースアロケーションに対して最初のO((\log T)^3)$の多対数後悔保証を達成できる慎重な丸み付き完全適応解法の両方を設計する。
我々のフレームワークは、最小限のオフラインデータ(周期毎に1つのサンプル)で操作し、変動予算の仮定なしで任意の非定常性を処理し、複数のリソース制約をサポートすることで、事前作業を進める。
関連論文リスト
- Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
我々は,シングルタイムスケールアクター・クリティック(AC)アルゴリズムを用いて,$O(-2)$の最適なグローバルポリシを得るための最適なサンプル複雑性を確立する。
これらのメカニズムは、既存のディープラーニングアーキテクチャと互換性があり、実用的な適用性を損なうことなく、小さな修正しか必要としない。
論文 参考訳（メタデータ） (2026-02-02T00:35:42Z) - VADE: Variance-Aware Dynamic Sampling via Online Sample-Level Difficulty Estimation for Multimodal RL [38.782188833641676]
GRPOやGSPOのようなグループベースのポリシー最適化手法は、マルチモーダルモデルのトレーニングの標準となっている。
グループ内のすべての応答が同じ報酬を受けると、それらは致命的な急激な消滅問題に悩まされる。
textbfVADEは,オンラインサンプルレベルの難易度を用いたサンプリングフレームワークである。
論文 参考訳（メタデータ） (2025-11-24T08:59:54Z) - Quantile-Optimal Policy Learning under Unmeasured Confounding [55.72891849926314]
ここでは,報酬分布が (0, 1) で最大$alpha$-quantileを持つポリシーを見つけることを目標とする量子最適政策学習について検討する。
このような問題は、(i)報酬分布の関数としての量子目標の非線形性、(ii)未観測の共起問題、(iii)オフラインデータセットのカバー不足という3つの大きな課題に悩まされている。
論文 参考訳（メタデータ） (2025-06-08T13:37:38Z) - Causality Pursuit from Heterogeneous Environments via Neural Adversarial Invariance Learning [12.947265104477237]
データから因果関係を抽出することは、科学的発見、治療介入、伝達学習における根本的な問題である。
本稿では,複数の環境における回帰モデルにおける非パラメトリック不変性と因果学習に対処するアルゴリズムを提案する。
提案したFocused Adrial Invariant Regularizationフレームワークは、逆検定により回帰モデルを予測不変解へ向ける革新的なミニマックス最適化手法を利用する。
論文 参考訳（メタデータ） (2024-05-07T23:37:40Z) - Non-Stochastic CDF Estimation Using Threshold Queries [3.6576781735746513]
実験的な分布を2つの課題で推定する問題に取り組む。
まず、アルゴリズムはデータを直接観察するのではなく、サンプルについて限られた数のしきい値クエリしか要求しない。
第二に、データは独立で同一の分散であると仮定されず、代わりにサンプルを生成する任意のプロセスが可能である。
論文 参考訳（メタデータ） (2023-01-13T18:00:57Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Online Selective Classification with Limited Feedback [82.68009460301585]
オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。
私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。
smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
論文 参考訳（メタデータ） (2021-10-27T08:00:53Z) - Solving Multistage Stochastic Linear Programming via Regularized Linear
Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
AdaSO(Adaptive least absolute shrinkage and selection operator)に基づく線形決定規則(LDR)の新しい正規化手法を提案する。
実験により、MSLPを解くために古典的な非正規化LDRを使用する場合、過度に適合する脅威は無視できないことが示された。
LHDP問題に対しては、非正規化ベンチマークと比較して、提案したフレームワークの次の利点を強調した。
論文 参考訳（メタデータ） (2021-10-07T02:36:14Z) - Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。
複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
論文 参考訳（メタデータ） (2020-10-21T13:43:48Z) - A Provably Efficient Sample Collection Strategy for Reinforcement
Learning [123.69175280309226]
オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。
1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
論文 参考訳（メタデータ） (2020-07-13T15:17:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。