論文の概要: Fully Dynamic Online Selection through Online Contention Resolution
Schemes
- arxiv url: http://arxiv.org/abs/2301.03099v1
- Date: Sun, 8 Jan 2023 19:35:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-10 15:55:18.948650
- Title: Fully Dynamic Online Selection through Online Contention Resolution
Schemes
- Title（参考訳）: オンラインコンテント解決方式による完全動的オンライン選択
- Authors: Vashist Avadhanula, Andrea Celli, Riccardo Colini-Baldeschi, Stefano
Leonardi, Matteo Russo
- Abstract要約: 逆/確率的環境下でのオンライン選択の完全動的問題について検討する。
対戦環境におけるオンライン選択問題に対するアプローチは、オンラインコンテント解決スキームの概念によって与えられる。
- 参考スコア（独自算出の注目度）: 15.149188998019186
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study fully dynamic online selection problems in an adversarial/stochastic
setting that includes Bayesian online selection, prophet inequalities, posted
price mechanisms, and stochastic probing problems subject to combinatorial
constraints. In the classical ``incremental'' version of the problem, selected
elements remain active until the end of the input sequence. On the other hand,
in the fully dynamic version of the problem, elements stay active for a limited
time interval, and then leave. This models, for example, the online matching of
tasks to workers with task/worker-dependent working times, and sequential
posted pricing of perishable goods. A successful approach to online selection
problems in the adversarial setting is given by the notion of Online Contention
Resolution Scheme (OCRS), that uses a priori information to formulate a linear
relaxation of the underlying optimization problem, whose optimal fractional
solution is rounded online for any adversarial order of the input sequence. Our
main contribution is providing a general method for constructing an OCRS for
fully dynamic online selection problems. Then, we show how to employ such OCRS
to construct no-regret algorithms in a partial information model with
semi-bandit feedback and adversarial inputs.
- Abstract（参考訳）: 本研究では,ベイズ的オンライン選択,預言不平等,ポスト価格機構,確率的探索問題を含む,対数的・確率的な環境下でのオンライン選択問題について検討する。
古典的な `incremental'' バージョンでは、選択された要素は入力シーケンスの終了までアクティブである。
一方、問題の完全な動的バージョンでは、要素は限られた時間間隔で活動し続け、それから去る。
このモデルは、例えば、タスク/ワーカーに依存した作業時間を持つ労働者に対するタスクのオンラインマッチングや、販売可能な商品の価格の逐次投稿といったものです。
オンライン競合解決スキーム (OCRS) は, オンライン競合解決スキーム (OCRS) の概念を用いて, 入力シーケンスの任意の逆順に対して, 最適分数解がオンラインに丸められている最適化問題の線形緩和を定式化したものである。
本研究の主な貢献は,完全動的オンライン選択問題に対するocrs構築のための汎用的手法を提供することである。
そして,このようなOCRSを用いて,半帯域フィードバックと逆入力を持つ部分情報モデルにおいて,非回帰アルゴリズムを構築する方法を示す。
関連論文リスト
- Online Influence Maximization: Concept and Algorithm [0.5801621787540268]
まず、オフラインIM問題を明確に定義する。
次に、オンラインIM問題と基本的なコンビニアル・マルチアーメッド・バンディット・フレームワークCMAB-Tの標準定義について述べる。
これはオンライン学習手法を用いてオンラインIM問題を解決する方法である。
論文 参考訳（メタデータ） (2023-11-30T15:24:05Z) - Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。
この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。
本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-31T22:59:23Z) - Online Nonsubmodular Minimization with Delayed Costs: From Full
Information to Bandit Feedback [98.7678704343537]
我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。
我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
論文 参考訳（メタデータ） (2022-05-15T08:27:12Z) - Dynamic Matching Bandit For Two-Sided Online Markets [13.185106969638877]
両面のオンラインマッチングプラットフォームは、様々な市場で採用されている。
現在の市場でのエージェントの好みは通常暗黙的で不明である。
本稿では,この動的オンラインマッチング問題に対して,文脈情報を用いた新しい枠組みを提案する。
論文 参考訳（メタデータ） (2022-05-07T18:28:20Z) - Optimal Data Selection: An Online Distributed View [61.31708750038692]
この問題のオンライン版と分散版のアルゴリズムを開発する。
ランダム選択法は, ランダム選択法よりも5～20%高い性能を示した。
ImageNet と MNIST の学習タスクにおいて、我々の選択方法はランダム選択よりも5-20% 高い性能を示した。
論文 参考訳（メタデータ） (2022-01-25T18:56:16Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Markov Decision Process modeled with Bandits for Sequential Decision
Making in Linear-flow [73.1896399783641]
会員/加入者の獲得と保持では、複数のページを連続してマーケティングコンテンツを推奨する必要がある。
遷移確率行列をモデル化するためにBandits を用いた MDP としてこの問題を定式化することを提案する。
提案したMDPのBanditsアルゴリズムは,$epsilon$-greedyと$epsilon$-greedy,$epsilon$,IndependentBandits,InteractionBanditsでQ-learningを上回っている。
論文 参考訳（メタデータ） (2021-07-01T03:54:36Z) - Online Adversarial Attacks [57.448101834579624]
我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。
まず、オンライン脅威モデルの決定論的変種を厳格に分析する。
このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
論文 参考訳（メタデータ） (2021-03-02T20:36:04Z) - Non-stationary Online Learning with Memory and Non-stochastic Control [71.14503310914799]
我々は,過去の決定に依拠する損失関数を許容するメモリを用いたオンライン凸最適化(OCO)の問題について検討する。
本稿では,非定常環境に対してロバストなアルゴリズムを設計するための性能指標として,動的ポリシーの後悔を紹介する。
我々は,時間的地平線,非定常度,メモリ長といった面で,最適な動的ポリシーの後悔を確実に享受するメモリ付きOCOの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-07T09:45:15Z) - The Best of Many Worlds: Dual Mirror Descent for Online Allocation
Problems [7.433931244705934]
本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。
様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。
我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
論文 参考訳（メタデータ） (2020-11-18T18:39:17Z) - Online Optimization with Memory and Competitive Control [43.974996526016305]
本稿では,メモリを用いたオンライン最適化問題に対する競合アルゴリズムを提案する。
本稿では,メモリによるオンライン最適化と,対向的障害を伴うオンライン制御の関連性を示す。
論文 参考訳（メタデータ） (2020-02-13T02:58:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。