論文の概要: Robust and Consistent Ski Rental with Distributional Advice

• arxiv url: http://arxiv.org/abs/2603.29233v1
• Date: Tue, 31 Mar 2026 04:04:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-01 15:25:03.136304
• Title: Robust and Consistent Ski Rental with Distributional Advice
• Title（参考訳）: 分布アドバイザを用いたロバストで一貫性のあるスキーレンタル
• Authors: Jihwan Kim, Chenglin Fan,
• Abstract要約: スキーレンタル問題は不確実性の下でのオンライン意思決定の標準モデルである。 本稿では,未知品質の分布的アドバイスを決定論的アルゴリズムとランダム化アルゴリズムの両方に統合するフレームワークを提案する。 我々のフレームワークは、既存の点予測ベースラインよりも一貫性を著しく向上し、かつ、同等の堅牢性を維持していることを示す。
• 参考スコア（独自算出の注目度）: 13.811651343801579
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The ski rental problem is a canonical model for online decision-making under uncertainty, capturing the fundamental trade-off between repeated rental costs and a one-time purchase. While classical algorithms focus on worst-case competitive ratios and recent "learning-augmented" methods leverage point-estimate predictions, neither approach fully exploits the richness of full distributional predictions while maintaining rigorous robustness guarantees. We address this gap by establishing a systematic framework that integrates distributional advice of unknown quality into both deterministic and randomized algorithms. For the deterministic setting, we formalize the problem under perfect distributional prediction and derive an efficient algorithm to compute the optimal threshold-buy day. We provide a rigorous performance analysis, identifying sufficient conditions on the predicted distribution under which the expected competitive ratio (ECR) matches the classic optimal randomized bound. To handle imperfect predictions, we propose the Clamp Policy, which restricts the buying threshold to a safe range controlled by a tunable parameter. We show that this policy is both robust, maintaining good performance even with large prediction errors, and consistent, approaching the optimal performance as predictions become accurate. For the randomized setting, we characterize the stopping distribution via a Water-Filling Algorithm, which optimizes expected cost while strictly satisfying robustness constraints. Experimental results across diverse distributions (Gaussian, geometric, and bi-modal) demonstrate that our framework improves consistency significantly over existing point-prediction baselines while maintaining comparable robustness.
• Abstract（参考訳）: スキーレンタル問題は不確実性の下でのオンライン意思決定の標準的なモデルであり、繰り返しのレンタルコストとワンタイム購入との間の基本的なトレードオフを捉えている。 古典的アルゴリズムは最悪の競合比率に焦点を合わせ、最近の"学習強化"手法はポイント推定予測を活用するが、どちらの手法も厳密な堅牢性を保証する一方で、完全な分布予測の豊かさを完全に活用しない。 未知品質の分布的アドバイスを決定論的アルゴリズムとランダム化アルゴリズムの両方に統合する体系的な枠組みを確立することで、このギャップに対処する。 決定論的設定のために、完全分布予測の下で問題を定式化し、最適なしきい値購入日を計算するための効率的なアルゴリズムを導出する。 予測競合比 (ECR) が古典的最適ランダム化境界と一致するような予測分布の十分な条件を特定する厳密な性能解析を行う。 不完全な予測に対処するため,購入閾値を調整可能なパラメータによって制御される安全な範囲に制限するクランプポリシーを提案する。 我々は,このポリシーが堅牢であり,大きな予測誤差があっても良好な性能を維持し,予測が正確になるにつれて最適な性能に近づきつつあることを示す。 ランダム化環境では, 強靭性制約を厳密に満たしつつ, 予測コストを最適化するWater-Filling Algorithmを用いて, 停止分布を特徴付ける。 種々の分布(ガウス,幾何,バイモーダル)にまたがる実験結果から,我々のフレームワークは,同等の頑健性を維持しつつ,既存の点予測ベースラインよりも一貫性を著しく向上することを示した。

関連論文リスト

• Deadline-Aware Online Scheduling for LLM Fine-Tuning with Spot Market Predictions [11.849924812127371]
  コスト効率のよいスケジューリングを可能にするための予測のパワーと、推定誤差に対する感度を示す。 本稿では,コミット型水平方向制御手法に基づくオンラインアロケーションアルゴリズムを提案する。 両アルゴリズムのパラメータを変動させて構築したプールから最良のポリシーを学習するオンラインポリシー選択アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-12-24T05:47:27Z)
• Distribution-informed Online Conformal Prediction [53.674678995825666]
  更新ルールに基礎となるデータパターンを組み込んだオンラインコンフォメーション予測アルゴリズムである Conformal Optimistic Prediction (COP) を提案する。 COPは予測可能なパターンが存在する場合により厳密な予測セットを生成し、見積もりが不正確な場合でも有効なカバレッジ保証を保持する。 我々は,COPが有効なカバレッジを実現し,他のベースラインよりも短い予測間隔を構築できることを証明した。
  論文  参考訳（メタデータ） (2025-12-08T17:51:49Z)
• Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach [4.702729080310267]
  時間的地平線上で正確な後続分布を維持する離散ベイズ的枠組みを提案する。 提案アルゴリズムは、事前依存した競合保証を達成し、最悪のケースと完全なインフォームド設定を優雅に補間する。 このフレームワークは、自然に複数の予測、一様でない事前情報、文脈情報を組み込むように拡張されている。
  論文  参考訳（メタデータ） (2025-12-08T08:56:25Z)
• Optimal Regularization Under Uncertainty: Distributional Robustness and Convexity Constraints [9.77322868877488]
  分布的に堅牢な最適正規化のためのフレームワークを導入する。 トレーニング分布の計算と均一な事前計算との間には,ロバストな正則化器がどのように介在するかを示す。
  論文  参考訳（メタデータ） (2025-10-03T19:35:38Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
  本稿では,各項目の品質の間隔推定に基づくランダム化意思決定の枠組みを提案する。 最適化に基づく最適化手法であるMERITを導入する。 MERITが既存のアプローチで保証されていない望ましい公理特性を満たすことを証明している。
  論文  参考訳（メタデータ） (2025-06-23T19:59:30Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。 本手法は, 精度の高い問題に特に適している。 提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
  論文  参考訳（メタデータ） (2023-11-08T00:10:21Z)
• Conformal Contextual Robust Optimization [21.2737854880866]
  データ駆動による確率論的意思決定問題を予測するアプローチは、安全クリティカルな設定における不確実な領域の不確実性のリスクを軽減することを目指している。 本稿では,CPO(Conformal-Then-Predict)フレームワークを提案する。 確率列最適化による意思決定問題。
  論文  参考訳（メタデータ） (2023-10-16T01:58:27Z)
• CovarianceNet: Conditional Generative Model for Correct Covariance Prediction in Human Motion Prediction [71.31516599226606]
  本稿では,将来の軌道の予測分布に関連する不確かさを正確に予測する手法を提案する。 我々のアプローチであるCovariaceNetは、ガウス潜在変数を持つ条件付き生成モデルに基づいている。
  論文  参考訳（メタデータ） (2021-09-07T09:38:24Z)

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

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