論文の概要: Ski Rental with Distributional Predictions of Unknown Quality

• arxiv url: http://arxiv.org/abs/2602.21104v1
• Date: Tue, 24 Feb 2026 17:03:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.854043
• Title: Ski Rental with Distributional Predictions of Unknown Quality
• Title（参考訳）: 未知品質の分布予測を用いたスキーレンタル
• Authors: Qiming Cui, Michael Dinitz,
• Abstract要約: 我々は「予測を伴うアルゴリズム」フレームワークにおいて、スキーレンタルの中央オンライン問題を再考する。 OPT + O(min(eta, 1) * sqrt(b), b log b) のコストが期待できるアルゴリズムが存在することを示す。 これらの境界は,予測誤差が0のときのO(sqrt(b)ロバスト性(付加損失)と予測誤差が任意に大きいときのO(b log b)ロバスト性を有する。
• 参考スコア（独自算出の注目度）: 3.162643581562756
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the central online problem of ski rental in the "algorithms with predictions" framework from the point of view of distributional predictions. Ski rental was one of the first problems to be studied with predictions, where a natural prediction is simply the number of ski days. But it is both more natural and potentially more powerful to think of a prediction as a distribution p-hat over the ski days. If the true number of ski days is drawn from some true (but unknown) distribution p, then we show as our main result that there is an algorithm with expected cost at most OPT + O(min(max({eta}, 1) * sqrt(b), b log b)), where OPT is the expected cost of the optimal policy for the true distribution p, b is the cost of buying, and {eta} is the Earth Mover's (Wasserstein-1) distance between p and p-hat. Note that when {eta} < o(sqrt(b)) this gives additive loss less than b (the trivial bound), and when {eta} is arbitrarily large (corresponding to an extremely inaccurate prediction) we still do not pay more than O(b log b) additive loss. An implication of these bounds is that our algorithm has consistency O(sqrt(b)) (additive loss when the prediction error is 0) and robustness O(b log b) (additive loss when the prediction error is arbitrarily large). Moreover, we do not need to assume that we know (or have any bound on) the prediction error {eta}, in contrast with previous work in robust optimization which assumes that we know this error. We complement this upper bound with a variety of lower bounds showing that it is essentially tight: not only can the consistency/robustness tradeoff not be improved, but our particular loss function cannot be meaningfully improved.
• Abstract（参考訳）: 我々は,分布予測の観点から,スキーレンタルのオンライン中心的課題である「予測付きアルゴリズム」の枠組みを再考する。 スキーレンタルは、自然の予測が単にスキーの日数であるような予測で研究された最初の問題の1つであった。 しかし、予想をスキーの日における分布p-hatと考えることは、より自然であり、潜在的に強力である。 真の(未知の)分布 p からスキーデーの真の数を引き出すと、OPT + O(min(max({eta}, 1) * sqrt(b, b log b)) が期待されるアルゴリズムが存在し、ここで OPT は真の分布 p に対する最適ポリシーの期待されるコスト、b は購入のコスト、{eta} は p-hat と p-hat の間のアースモーバー距離であることを示す。 ここで {eta} < o(sqrt(b)) が b 未満の加法損失を与えるとき(自明な境界)、 {eta} が任意に大きいとき(非常に不正確な予測に対応する)、我々はまだ O(b log b) 加法損失以上を払わない。 これらの境界の1つの意味は、我々のアルゴリズムが整合性O(sqrt(b))(予測誤差が0のとき加法的損失)とロバスト性O(b log b)(予測誤差が任意に大きいとき加法的損失)を持つことである。 さらに、我々は予測誤差 {eta} を知っている(あるいは何らかの境界がある)と仮定する必要はなく、この誤差を知っていると仮定するロバストな最適化における以前の研究とは対照的である。 我々は、この上界を、それが本質的に密であることを示す様々な下界で補完する: 一貫性/損益性トレードオフを改善できないだけでなく、我々の特定の損失関数を有意に改善できない。

関連論文リスト

• Monitoring State Transitions in Markovian Systems with Sampling Cost [65.4151496405543]
  自然なアプローチは、予想される予測損失がクエリコスト以下で、クエリがなければいつ発生するかを予測する、欲張りのポリシーである。 最適(OPT)戦略は状態依存のしきい値ポリシである。 遷移確率が未知の場合、我々は、グレディポリシーの予測勾配降下(PSGD)に基づく学習変種を提案する。
  論文  参考訳（メタデータ） (2025-10-25T15:07:37Z)
• Online Prediction with Limited Selectivity [8.540426791244535]
  多くのデータ統計は、分布的な仮定や専門家のアドバイスなしに、非自明なエラー率に予測できる。 本稿では,予測者が時間軸のサブセットでのみ予測を開始することができる限定選択性付き予測(PLS)モデルを提案する。 本稿では,インスタンス・バイ・インスタンス・ベースと平均ケース・アナリティクスの両方を用いて最適予測誤差について検討する。
  論文  参考訳（メタデータ） (2025-08-13T08:17:12Z)
• Optimal Conformal Prediction under Epistemic Uncertainty [61.46247583794497]
  コンフォーマル予測(CP)は不確実性を表すための一般的なフレームワークである。 条件付きカバレッジを保証する最小の予測セットを生成するBernoulli予測セット(BPS)を導入する。 1次予測を与えられた場合、BPSはよく知られた適応予測セット(APS)に還元する。
  論文  参考訳（メタデータ） (2025-05-25T08:32:44Z)
• Fair Secretaries with Unfair Predictions [12.756552522270198]
  予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。 私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
  論文  参考訳（メタデータ） (2024-11-15T00:23:59Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。 適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
  論文  参考訳（メタデータ） (2024-05-24T11:22:19Z)
• The One-Inclusion Graph Algorithm is not Always Optimal [11.125968799758436]
  本稿では,Vapnik-Chervonenkisクラスに対する探索的一括グラフアルゴリズムを提案する。 我々は,近年の予測手法により,同じ低い高確率性能が継承されていることを示す。
  論文  参考訳（メタデータ） (2022-12-19T06:49:39Z)
• Uncertainty estimation of pedestrian future trajectory using Bayesian approximation [137.00426219455116]
  動的トラフィックシナリオでは、決定論的予測に基づく計画は信頼できない。 著者らは、決定論的アプローチが捉えられない近似を用いて予測中の不確実性を定量化する。 将来の状態の不確実性に対する降雨重量と長期予測の影響について検討した。
  論文  参考訳（メタデータ） (2022-05-04T04:23:38Z)
• Sequential prediction under log-loss and misspecification [47.66467420098395]
  累積的後悔の観点から,ログロスに基づく逐次予測の問題を考える。 明確に特定され誤記された症例の累積的後悔が偶然に現れる。 分布自由あるいはPAC後悔を$o(1)$で特徴づける。
  論文  参考訳（メタデータ） (2021-01-29T20:28:23Z)
• Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors [3.5788754401889014]
  有界ユークリッド球における正方形損失に対する予測問題と最良の線形予測器について検討する。 最小二乗推定器に対する$O(d/n)$過剰リスク率を保証するのに十分な分布仮定について論じる。
  論文  参考訳（メタデータ） (2020-09-19T21:39:46Z)
• Malicious Experts versus the multiplicative weights algorithm in online prediction [85.62472761361107]
  2人の専門家と1人の予測者による予測問題を考える。 専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。 もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
  論文  参考訳（メタデータ） (2020-03-18T20:12:08Z)

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

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