論文の概要: Programming by Rewards
- arxiv url: http://arxiv.org/abs/2007.06835v1
- Date: Tue, 14 Jul 2020 05:49:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-10 13:31:36.175905
- Title: Programming by Rewards
- Title（参考訳）: Rewardsによるプログラミング
- Authors: Nagarajan Natarajan, Ajaykrishna Karthikeyan, Prateek Jain, Ivan
Radicek, Sriram Rajamani, Sumit Gulwani, Johannes Gehrke
- Abstract要約: 我々は、性能、資源利用、あるいはベンチマーク上の正確性などの量的指標を最適化するための新しいアプローチである「報酬によるプログラミング」 (PBR) を定式化し、研究する。
PBR仕様は、(1)入力機能$x$と(2)報酬関数$r$で構成され、ブラックボックスコンポーネントとしてモデル化されている(実行しかできない)。
フレームワークは理論的に確立された -- 報酬が優れた特性を満たす場合において、合成されたコードは正確な意味で最適であることを示す。
- 参考スコア（独自算出の注目度）: 20.626369097817715
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We formalize and study ``programming by rewards'' (PBR), a new approach for
specifying and synthesizing subroutines for optimizing some quantitative metric
such as performance, resource utilization, or correctness over a benchmark. A
PBR specification consists of (1) input features $x$, and (2) a reward function
$r$, modeled as a black-box component (which we can only run), that assigns a
reward for each execution. The goal of the synthesizer is to synthesize a
"decision function" $f$ which transforms the features to a decision value for
the black-box component so as to maximize the expected reward $E[r \circ f
(x)]$ for executing decisions $f(x)$ for various values of $x$. We consider a
space of decision functions in a DSL of loop-free if-then-else programs, which
can branch on linear functions of the input features in a tree-structure and
compute a linear function of the inputs in the leaves of the tree. We find that
this DSL captures decision functions that are manually written in practice by
programmers. Our technical contribution is the use of continuous-optimization
techniques to perform synthesis of such decision functions as if-then-else
programs. We also show that the framework is theoretically-founded ---in cases
when the rewards satisfy nice properties, the synthesized code is optimal in a
precise sense.
We have leveraged PBR to synthesize non-trivial decision functions related to
search and ranking heuristics in the PROSE codebase (an industrial strength
program synthesis framework) and achieve competitive results to manually
written procedures over multiple man years of tuning. We present empirical
evaluation against other baseline techniques over real-world case studies
(including PROSE) as well on simple synthetic benchmarks.
- Abstract（参考訳）: PBR(Programming by rewards)は,パフォーマンスや資源利用,あるいはベンチマーク上の正当性などの定量的指標を最適化するために,サブルーチンを指定・合成するための新しい手法である。
PBR仕様は(1)入力機能$x$、(2)報酬関数$r$で、ブラックボックスコンポーネントとしてモデル化され、実行毎に報酬を割り当てる。
シンセサイザーの目標は「決定関数」$f$を合成することであり、ブラックボックスコンポーネントの判断値を変換して、様々な値の$x$に対して$f(x)$を実行するための期待報酬$e[r \circ f(x)]$を最大化することである。
我々は,木構造における入力特徴の線形関数を分岐し,木の葉における入力の線形関数を計算するループフリーif-then-elseプログラムのdslにおける決定関数の空間を考える。
このdslはプログラマが実際に手作業で記述した決定関数をキャプチャする。
我々の技術的貢献は、if-then-elseプログラムのような決定関数の合成に連続最適化技術を使うことである。
また、このフレームワークは理論的に確立された -- 報酬が優れた特性を満たす場合において、合成されたコードは正確な意味で最適であることを示す。
我々は,pbrを活用して,proseコードベースにおける検索・ランキングヒューリスティックスに関連する非自明な決定関数(産業強度プログラム合成フレームワーク)を合成し,複数人のチューニングにおいて手作業による手続きと競合する結果を得る。
実世界のケーススタディ(PROSEを含む)と単純な合成ベンチマークにおいて,他のベースライン技術に対する実証評価を行った。
関連論文リスト
- Composite Bayesian Optimization In Function Spaces Using NEON -- Neural Epistemic Operator Networks [4.1764890353794994]
NEONは、単一のオペレータネットワークバックボーンを使用して不確実性のある予測を生成するアーキテクチャである。
NEONは、トレーニング可能なパラメータを桁違いに減らしながら、最先端のパフォーマンスを実現していることを示す。
論文 参考訳（メタデータ） (2024-04-03T22:42:37Z) - BOIS: Bayesian Optimization of Interconnected Systems [0.0]
BOにおける複合関数の効率的な利用を可能にする新しいパラダイムを提案する。
この単純なアプローチ(BOISと呼ぶ)が構造的知識の活用を可能にしていることを示す。
以上の結果から,BOISが性能向上を実現し,複合関数の統計を正確に把握できることが示唆された。
論文 参考訳（メタデータ） (2023-11-19T06:44:13Z) - Bayesian Optimization for Function Compositions with Applications to
Dynamic Pricing [0.0]
本稿では, 構成の形式が知られているが, 構成関数を評価するのに費用がかかる機能構成の実用的BO法を提案する。
本稿では,収益管理における動的価格設定への新たな応用を,その基盤となる需要関数の評価に費用がかかる場合に示す。
論文 参考訳（メタデータ） (2023-03-21T15:45:06Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳（メタデータ） (2022-12-12T18:58:59Z) - Efficient computation of the Knowledge Gradient for Bayesian
Optimization [1.0497128347190048]
One-shot Hybrid KGは、これまで提案されていたアイデアをいくつか組み合わせた新しいアプローチであり、計算が安価で、強力で効率的である。
すべての実験はBOTorchで実施され、同等または改善された性能で計算オーバーヘッドを劇的に削減した。
論文 参考訳（メタデータ） (2022-09-30T10:39:38Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Reward Machines: Exploiting Reward Function Structure in Reinforcement
Learning [22.242379207077217]
報酬関数のコードをRLエージェントに示すことで、関数の内部構造を利用して最適なポリシーを学習する方法を示す。
まず、報酬関数の仕様をサポートする有限状態機械の一種である報酬機械を提案する。
次に、この構造を利用して、自動報酬形成、タスク分解、非政治的学習による対実的推論など、学習を支援する方法について述べる。
論文 参考訳（メタデータ） (2020-10-06T00:10:16Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。