論文の概要: Adaptive maximization of social welfare
- arxiv url: http://arxiv.org/abs/2310.09597v1
- Date: Sat, 14 Oct 2023 15:09:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 02:08:30.884754
- Title: Adaptive maximization of social welfare
- Title（参考訳）: 社会福祉の適応的最大化
- Authors: Nicolo Cesa-Bianchi and Roberto Colomboni and Maximilian Kasy
- Abstract要約: 我々は、社会福祉を最大化するための政策を繰り返し選択する問題を考える。
我々は, Exp3アルゴリズムの変形に対して, 後悔に対する低い境界と, 一致する逆上界を導出する。
- 参考スコア（独自算出の注目度）: 1.7495213911983416
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We consider the problem of repeatedly choosing policies to maximize social
welfare. Welfare is a weighted sum of private utility and public revenue.
Earlier outcomes inform later policies. Utility is not observed, but indirectly
inferred. Response functions are learned through experimentation.
We derive a lower bound on regret, and a matching adversarial upper bound for
a variant of the Exp3 algorithm. Cumulative regret grows at a rate of
$T^{2/3}$. This implies that (i) welfare maximization is harder than the
multi-armed bandit problem (with a rate of $T^{1/2}$ for finite policy sets),
and (ii) our algorithm achieves the optimal rate. For the stochastic setting,
if social welfare is concave, we can achieve a rate of $T^{1/2}$ (for
continuous policy sets), using a dyadic search algorithm.
We analyze an extension to nonlinear income taxation, and sketch an extension
to commodity taxation. We compare our setting to monopoly pricing (which is
easier), and price setting for bilateral trade (which is harder).
- Abstract（参考訳）: 社会福祉を最大化するための政策を繰り返し選択する問題を考える。
福祉は民間の公益と公益の重み付けである。
初期の結果は後続の政策を知らせる。
実用性は観察されていないが、間接的に推測される。
応答関数は実験を通じて学習される。
我々は, Exp3アルゴリズムの変形に対して, 後悔に対する低い境界と, 一致する逆上界を導出する。
累積的な後悔は$t^{2/3}$で増加する。
これが意味する。
(i)福祉の最大化は、多武装バンディット問題(有限政策集合に対して$t^{1/2}$)よりも困難である。
(ii)このアルゴリズムは最適速度を達成する。
確率的な設定では、社会福祉が凹凸であれば、dyadic searchアルゴリズムを用いて、(連続的な政策集合に対して)$t^{1/2}$ の率を達成できる。
我々は、非線形所得課税の拡張を分析し、商品課税の拡張をスケッチする。
我々は、われわれの設定を独占価格(これは簡単)と二国間貿易(より難しい)の価格設定と比較する。
関連論文リスト
- Oracle-Efficient Reinforcement Learning for Max Value Ensembles [7.404901768256101]
大または無限の状態空間における強化学習(RL)は、理論上、実験的に困難である。
この作業では、$textitmax-following Policy$と競合することを目指しています。
我々の主な成果は、構成ポリシーのみにアクセスすると、最大フォローポリシーと競合する効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2024-05-27T01:08:23Z) - Bayesian Online Multiple Testing: A Resource Allocation Approach [21.23710184381363]
本研究では,各実験が仮説テストタスクに対応する連続的な実験を行うことの問題点を考察する。
目的は、ローカル・ファルス・ディスカバリー・レート(LFDR)で測定された全ての時点において、低いエラー率を維持しながら発見回数を最大化することである。
予算安全バッファを組み込んだ新しいポリシーを提案する。
論文 参考訳（メタデータ） (2024-02-18T02:11:54Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Best of Both Worlds Policy Optimization [33.13041034490332]
本稿では,正則化器,探索ボーナス,学習率を適切に設計することにより,損失が相反する場合には,より好意的なポリログ$(T)=後悔が得られることを示す。
政策最適化のために、ギャップ依存のポリログ$(T)$後悔境界が示されるのはこれが初めてである。
論文 参考訳（メタデータ） (2023-02-18T19:46:11Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Restless Bandits with Many Arms: Beating the Central Limit Theorem [25.639496138046546]
有限ホライズン・レスト・ブレイディット(有限ホライズン・レスト・ブレイディット)は、レコメンデーターシステム、アクティブラーニング、収益管理、その他多くの分野で重要な役割を果たしている。
最適ポリシーは、原理的には動的プログラミングを用いて計算できるが、計算に必要なスケールは腕数$N$で指数関数的にスケールする。
最適性ギャップが$O(1)$である流体プライオリティポリシと呼ばれる、非退化条件と、実用的に計算可能な新しいポリシーのクラスを特徴付ける。
論文 参考訳（メタデータ） (2021-07-25T23:27:12Z) - State Augmented Constrained Reinforcement Learning: Overcoming the
Limitations of Learning with Rewards [88.30521204048551]
制約付き強化学習の一般的な定式化には、与えられた閾値に個別に蓄積しなければならない複数の報酬が含まれる。
ここでは,任意の重み付けされた報酬の線形結合によって,所望の最適政策を誘導できない簡単な例を示す。
この研究は、ラグランジュ乗算器で状態を増大させ、原始双対法を再解釈することで、この欠点に対処する。
論文 参考訳（メタデータ） (2021-02-23T21:07:35Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z) - Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。
我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
論文 参考訳（メタデータ） (2020-02-19T15:41:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。