論文の概要: Learning While Repositioning in On-Demand Vehicle Sharing Networks
- arxiv url: http://arxiv.org/abs/2501.19208v1
- Date: Fri, 31 Jan 2025 15:16:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-03 14:02:45.906284
- Title: Learning While Repositioning in On-Demand Vehicle Sharing Networks
- Title（参考訳）: オンデマンドカーシェアリングネットワークにおける再配置中の学習
- Authors: Hansheng Jiang, Chunlin Sun, Zuo-Jun Max Shen, Shunan Jiang,
- Abstract要約: 我々は、一方通行のオンデマンド車両共有サービスによるネットワーク在庫問題を考える。
自然なリプシッツ帯域法が$widetildeO(Tfracnn+1)$の後悔の保証を達成できることを示し、これは$n$に対する指数的依存に悩まされる。
これらの課題に乗じて、検閲された需要のみに依存するオンライン・グラディエント・リポジション・アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 4.724825031148413
- License:
- Abstract: We consider a network inventory problem motivated by one-way, on-demand vehicle sharing services. Due to uncertainties in both demand and returns, as well as a fixed number of rental units across an $n$-location network, the service provider must periodically reposition vehicles to match supply with demand spatially while minimizing costs. The optimal repositioning policy under a general $n$-location network is intractable without knowing the optimal value function. We introduce the best base-stock repositioning policy as a generalization of the classical inventory control policy to $n$ dimensions, and establish its asymptotic optimality in two distinct limiting regimes under general network structures. We present reformulations to efficiently compute this best base-stock policy in an offline setting with pre-collected data. In the online setting, we show that a natural Lipschitz-bandit approach achieves a regret guarantee of $\widetilde{O}(T^{\frac{n}{n+1}})$, which suffers from the exponential dependence on $n$. We illustrate the challenges of learning with censored data in networked systems through a regret lower bound analysis and by demonstrating the suboptimality of alternative algorithmic approaches. Motivated by these challenges, we propose an Online Gradient Repositioning algorithm that relies solely on censored demand. Under a mild cost-structure assumption, we prove that it attains an optimal regret of $O(n^{2.5} \sqrt{T})$, which matches the regret lower bound in $T$ and achieves only polynomial dependence on $n$. The key algorithmic innovation involves proposing surrogate costs to disentangle intertemporal dependencies and leveraging dual solutions to find the gradient of policy change. Numerical experiments demonstrate the effectiveness of our proposed methods.
- Abstract（参考訳）: 我々は、一方通行のオンデマンド車両共有サービスによるネットワーク在庫問題を考える。
需要とリターンの不確実性、および$n$-locationネットワーク上の固定数のレンタルユニットのため、サービス提供者は、コストを最小化しつつ、需要と供給を空間的に一致させるために定期的に車両を配置する必要がある。
一般的な$n$-locationネットワークの下での最適再配置ポリシーは、最適値関数を知らずに難解である。
本稿では,古典的在庫管理ポリシを$n$次元に一般化した上で,その漸近的最適性を,一般的なネットワーク構造の下での2つの異なる制限体制において確立する。
我々は、この最良基準ストックポリシーを、事前収集されたデータを用いてオフラインで効率的に計算する修正を提案する。
オンライン設定では、自然なリプシッツ・バンドイットアプローチが$\widetilde{O}(T^{\frac{n}{n+1}})$の後悔の保証を達成することを示す。
本稿では,ネットワークシステムにおける検閲データを用いた学習の課題について,再帰的低境界解析と,代替アルゴリズムアプローチの準最適性を示すことによって説明する。
これらの課題に乗じて、検閲された需要のみに依存するオンライン・グラディエント・リポジション・アルゴリズムを提案する。
軽度のコスト構造仮定の下では、$O(n^{2.5} \sqrt{T})$の最適後悔を達成し、$T$の後悔の下限と一致し、$n$の多項式依存しか達成しないことを示す。
重要なアルゴリズムの革新は、時間的依存関係を解消するために代理コストを提案し、ポリシー変更の勾配を見つけるために2つのソリューションを活用することである。
提案手法の有効性を示す数値実験を行った。
関連論文リスト
- Iterative Reweighted Least Squares Networks With Convergence Guarantees
for Solving Inverse Imaging Problems [12.487990897680422]
解析に基づく画像正規化における画像再構成タスクの新しい最適化手法を提案する。
そのような正規化子は $ell_pp$-vector および $mathcalS_pp$ Schatten-matrix 準ノルムの重み付き拡張に対応するポテンシャル関数を用いてパラメータ化する。
提案する最小化戦略の収束保証により,メモリ効率の高い暗黙バックプロパゲーション方式により,そのような最適化を成功させることができることを示す。
論文 参考訳（メタデータ） (2023-08-10T17:59:46Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳（メタデータ） (2023-05-30T16:05:44Z) - Offline Primal-Dual Reinforcement Learning for Linear MDPs [16.782625445546273]
オフライン強化学習(RL)は、他のポリシによって収集されたトランジションの固定データセットから、ほぼ最適なポリシを学ぶことを目的としている。
本稿では,RLの線形プログラミング定式化に基づく原始双対最適化手法を提案する。
論文 参考訳（メタデータ） (2023-05-22T11:45:23Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
論文 参考訳（メタデータ） (2023-02-02T16:30:33Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。
本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。
この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
論文 参考訳（メタデータ） (2022-09-16T09:38:38Z) - Globally Convergent Policy Search over Dynamic Filters for Output
Estimation [64.90951294952094]
我々は,大域的に最適な$textitdynamic$ filterに収束する最初の直接ポリシー探索アルゴリズム凸を導入する。
我々は、情報化が前述の優越性を克服していることを示す。
論文 参考訳（メタデータ） (2022-02-23T18:06:20Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds
Globally Optimal Policy [95.98698822755227]
本研究は,リスクに敏感な深層強化学習を,分散リスク基準による平均報酬条件下で研究する試みである。
本稿では,ポリシー,ラグランジュ乗算器,フェンシェル双対変数を反復的かつ効率的に更新するアクタ批判アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-28T05:02:26Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳（メタデータ） (2020-12-13T04:47:37Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。