論文の概要: Logarithmic Regret in Multisecretary and Online Linear Programming
Problems with Continuous Valuations
- arxiv url: http://arxiv.org/abs/1912.08917v5
- Date: Sun, 20 Aug 2023 03:56:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-23 03:41:55.832150
- Title: Logarithmic Regret in Multisecretary and Online Linear Programming
Problems with Continuous Valuations
- Title（参考訳）: 連続評価を伴う複数秘密・オンライン線形計画問題における対数回帰
- Authors: Robert L. Bray
- Abstract要約: 私は、nドル以上の顧客がnドル以上の期間に順次到着する一般的な収益管理問題を研究します。
satifying the period-$ t $ yields utility $ u_t in mathbbR_+ $ and the inventory holds by $ A_t in mathbbR_++M $.
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: I study a general revenue management problem in which $ n $ customers arrive
sequentially over $ n $ periods, and you must dynamically decide which to
satisfy. Satisfying the period-$ t $ customer yields utility $ u_{t} \in
\mathbb{R}_{+} $ and decreases your inventory holdings by $ A_{t} \in
\mathbb{R}_{+}^{M} $. The customer vectors, $ (u_{t}, A_{t}')' $, are i.i.d.,
with $ u_{t} $ drawn from a finite-mean continuous distribution and $ A_{t} $
drawn from a bounded discrete or continuous distribution. I study this system's
regret, which is the additional utility you could get if you didn't have to
make decisions on the fly. I show that if your initial inventory endowment
scales linearly with $ n $ then your expected regret is $ \Theta(\log(n)) $ as
$ n \rightarrow \infty $. I provide a simple policy that achieves this $
\Theta(\log(n)) $ regret rate. Finally, I extend this result to Arlotto and
Gurich's (2019) multisecretary problem with uniformly distributed secretary
valuations.
- Abstract（参考訳）: 私は、$n$の顧客が$n$の期間に順次到着する一般的な収益管理問題を研究します。
期間を満たせば、ユーティリティ$ u_{t} \in \mathbb{r}_{+} $ となり、在庫持ち分を$ a_{t} \in \mathbb{r}_{+}^{m} $ に減らす。
顧客ベクトル $ (u_{t}, a_{t}')' は i.i.d. で、$ u_{t} $ は有限平均連続分布から、$ a_{t} $ は有界離散分布または連続分布から引き出される。
私はこのシステムの後悔を研究しています。それは、あなたがすぐに決定する必要がない場合に得られる追加のユーティリティです。
初期在庫が$n$で線形にスケールした場合、期待される後悔は$ \Theta(\log(n)) $ as $ n \rightarrow \infty $である。
この$ \Theta(\log(n)) $ regret rate を達成するためのシンプルなポリシーを提供します。
最後に、私はこの結果をarlotto氏とgurich氏(2019)のマルチセクタリー問題に拡張します。
関連論文リスト
- Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations [17.957489763446496]
次元 $Theta において、$mathbbZ/qmathbbZ$ 上の雑音線型方程式を解くことによる時間短縮を提案する。
密接な問題からスパース問題の硬さを推定する。
論文 参考訳（メタデータ） (2024-11-19T13:53:43Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。
改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
論文 参考訳（メタデータ） (2023-05-24T17:40:57Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳（メタデータ） (2023-02-01T05:22:40Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z) - Logistic Regression Regret: What's the Catch? [3.7311680121118345]
パラメータに対する$L_infty$制約の下で、対数的後悔を伴う下界を導出する。
L$の制約については、十分に大きな$d$の場合、後悔は$d$で線形であるが、$T$で対数化されなくなることが示されている。
論文 参考訳（メタデータ） (2020-02-07T18:36:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。