論文の概要: On Satisficing in Quantitative Games
- arxiv url: http://arxiv.org/abs/2101.02594v1
- Date: Wed, 6 Jan 2021 07:47:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-11 06:38:35.540241
- Title: On Satisficing in Quantitative Games
- Title（参考訳）: 量的ゲームにおける満足感について
- Authors: Suguman Bansal, Krishnendu Chatterjee, Moshe Y. Vardi
- Abstract要約: 本研究は,割引コストモデルを用いた2プレイヤーグラフゲームにおける満足度問題を定義し,検討する。
最適化問題と同様に数値手法で満足度を解くことができるが、この手法は最適化よりも説得力のある利点を示さない。
- 参考スコア（独自算出の注目度）: 30.53498001438171
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Several problems in planning and reactive synthesis can be reduced to the
analysis of two-player quantitative graph games. {\em Optimization} is one form
of analysis. We argue that in many cases it may be better to replace the
optimization problem with the {\em satisficing problem}, where instead of
searching for optimal solutions, the goal is to search for solutions that
adhere to a given threshold bound.
This work defines and investigates the satisficing problem on a two-player
graph game with the discounted-sum cost model. We show that while the
satisficing problem can be solved using numerical methods just like the
optimization problem, this approach does not render compelling benefits over
optimization. When the discount factor is, however, an integer, we present
another approach to satisficing, which is purely based on automata methods. We
show that this approach is algorithmically more performant -- both
theoretically and empirically -- and demonstrates the broader applicability of
satisficing overoptimization.
- Abstract（参考訳）: 計画と反応合成に関するいくつかの問題は、2人のプレイヤーによる定量的グラフゲームの分析に還元できる。
最適化とは分析の一形態である。
多くの場合、最適化問題を最適な解を探す代わりに、与えられたしきい値に従属する解を探索することが目的であるような {\em satisficing problem} に置き換えた方がよいと論じる。
本研究は,割引コストモデルを用いた2プレイヤーグラフゲームにおける満足度問題を定義し,検討する。
最適化問題と同様に数値手法で満足度を解くことができるが、この手法は最適化よりも説得力のある利点を示さない。
しかし、割引係数が整数である場合には、純粋にオートマトン法に基づく満足度に対する別のアプローチを示す。
このアプローチは、理論的にも経験的にもアルゴリズム的にもよりパフォーマンスが高く、過剰最適化を満足する幅広い適用性を示している。
関連論文リスト
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Instance Specific Approximations for Submodular Maximization [45.91235224228292]
実世界のインスタンス上で最適な解に対して,アルゴリズムの性能をベンチマークする手法を模索する。
大きな疑問は、実際に遭遇したインスタンスの最適なソリューションと比較して、アルゴリズムのパフォーマンスを測定する方法です。
我々の主な貢献は、サブモジュラー最小化のための新しいアルゴリズムではなく、サブモジュラーインスタンスのアルゴリズムがいかに最適かを測定する分析手法である。
論文 参考訳（メタデータ） (2021-02-23T19:39:32Z) - Slowly Varying Regression under Sparsity [5.22980614912553]
本稿では, 緩やかな過度回帰の枠組みを提示し, 回帰モデルが緩やかかつスパースな変動を示すようにした。
本稿では,バイナリ凸アルゴリズムとして再構成する手法を提案する。
結果として得られたモデルは、様々なデータセット間で競合する定式化よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-02-22T04:51:44Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
ワッサーシュタイン推定器勾配の正規化版を、自然次元のサブ線形なステップ毎の時間で解くアルゴリズムを導入する。
このアルゴリズムは他のタスクにも拡張可能であることを示し、その中にはWasserstein Barycentersの推定も含まれる。
論文 参考訳（メタデータ） (2020-02-20T12:04:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。