論文の概要: A Reinforcement Learning based Reset Policy for CDCL SAT Solvers

• arxiv url: http://arxiv.org/abs/2404.03753v1
• Date: Thu, 4 Apr 2024 18:44:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-08 17:35:40.868381
• Title: A Reinforcement Learning based Reset Policy for CDCL SAT Solvers
• Title（参考訳）: 強化学習に基づくCDCL SATソルバーのリセットポリシー
• Authors: Chunxiao Li, Charlie Liu, Jonathan Chung, Zhengyang, Lu, Piyush Jha, Vijay Ganesh,
• Abstract要約: 再起動の変種であるリセットがCDCLソルバに与える影響について検討する。 リセット政策は、武器を適応的に選択することで、探索と探索のトレードオフのバランスをとる。 部分的リセットの概念を導入し、少なくとも一定数の可変アクティビティが保持される。
• 参考スコア（独自算出の注目度）: 12.3586388203336
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Restart policy is an important technique used in modern Conflict-Driven Clause Learning (CDCL) solvers, wherein some parts of the solver state are erased at certain intervals during the run of the solver. In most solvers, variable activities are preserved across restart boundaries, resulting in solvers continuing to search parts of the assignment tree that are not far from the one immediately prior to a restart. To enable the solver to search possibly "distant" parts of the assignment tree, we study the effect of resets, a variant of restarts which not only erases the assignment trail, but also randomizes the activity scores of the variables of the input formula after reset, thus potentially enabling a better global exploration of the search space. In this paper, we model the problem of whether to trigger reset as a multi-armed bandit (MAB) problem, and propose two reinforcement learning (RL) based adaptive reset policies using the Upper Confidence Bound (UCB) and Thompson sampling algorithms. These two algorithms balance the exploration-exploitation tradeoff by adaptively choosing arms (reset vs. no reset) based on their estimated rewards during the solver's run. We implement our reset policies in four baseline SOTA CDCL solvers and compare the baselines against the reset versions on Satcoin benchmarks and SAT Competition instances. Our results show that RL-based reset versions outperform the corresponding baseline solvers on both Satcoin and the SAT competition instances, suggesting that our RL policy helps to dynamically and profitably adapt the reset frequency for any given input instance. We also introduce the concept of a partial reset, where at least a constant number of variable activities are retained across reset boundaries. Building on previous results, we show that there is an exponential separation between O(1) vs. $\Omega(n)$-length partial resets.
• Abstract（参考訳）: リスタートポリシは、現代の衝突駆動クローズラーニング(CDCL)ソルバで使用される重要なテクニックであり、ソルバ状態の一部が、ソルバの実行中に一定間隔で消去される。 ほとんどのソルバでは、変数のアクティビティは再起動バウンダリを越えて保存されるため、ソルバは再起動直前のアサインツリーの一部の検索を継続する。 代入木の「距離」のある部分の探索を可能にするために,代入軌跡を消去するだけでなく,再セット後の入力公式の変数の活性スコアをランダム化し,検索空間のより優れたグローバルな探索を可能にするリセットの効果について検討する。 本稿では、マルチアームバンディット(MAB)問題としてリセットをトリガするかどうかをモデル化し、アッパー信頼境界(UCB)とトンプソンサンプリングアルゴリズムを用いた2つの強化学習(RL)に基づく適応リセットポリシーを提案する。 これらの2つのアルゴリズムは、解法の実行中に推定された報酬に基づいてアーム(リセット対リセット)を適応的に選択することで、探索-探索トレードオフのバランスをとる。 我々は4つのベースラインSOTA CDCLソルバにリセットポリシーを実装し、ベースラインをSatcoinベンチマークとSATコンペティションインスタンスのリセットバージョンと比較する。 その結果, RL ベースのリセットバージョンは Satcoin と SAT の競合インスタンスで対応するベースラインソルバよりも優れており, RL ポリシーは任意の入力インスタンスに対してリセット頻度を動的に, 収益的に適応させるのに役立つことが示唆された。 また、部分的リセットの概念を導入し、少なくとも一定の数の変数アクティビティがリセット境界を越えて保持される。 以前の結果に基づいて、O(1) 対 $\Omega(n)$-長部分リセットの間に指数的分離が存在することを示す。

関連論文リスト

• Stochastic Bandits with ReLU Neural Networks [40.41457480347015]
  我々は,1層ReLUニューラルネットワークの帯域を考慮すれば,$tildeO(sqrtT)の後悔保証が達成可能であることを示す。 この上限を達成できるOFU-ReLUアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-12T16:54:57Z)
• State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewards [18.0878149546412]
  本論文は,前回腕を抜いた時から経過したラウンド数に依存する包帯の回復設定について考察する。 本稿では, ラウンドを状態として扱う状態分離SARSA(State-Separate SARSA)アルゴリズムという, この設定に適した新しい強化学習法を提案する。
  論文  参考訳（メタデータ） (2024-03-18T07:14:21Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• Provable Reset-free Reinforcement Learning by No-Regret Reduction [13.800970428473134]
  本稿では,リセットフリーなRLアルゴリズムを体系的に設計する汎用的ノ・レグレット還元法を提案する。 我々の減少はリセットのないRL問題を2プレーヤゲームに変える。 この2プレイヤーゲームにおいてサブリニア後悔を達成することは、元のRL問題においてサブリニア性能後悔とサブリニア総リセット数の両方を持つポリシーを学ぶことを意味する。
  論文  参考訳（メタデータ） (2023-01-06T05:51:53Z)
• A State-Distribution Matching Approach to Non-Episodic Reinforcement Learning [61.406020873047794]
  現実世界の応用への大きなハードルは、エピソード的な環境でのアルゴリズムの開発である。 提案手法は,提案する実証実験における状態分布に一致するように後方方針を訓練する手法である。 実験の結果,MEDALは3つのスパース・リワード連続制御タスクにおいて先行手法と一致し,性能が向上することがわかった。
  論文  参考訳（メタデータ） (2022-05-11T00:06:29Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Supervised Advantage Actor-Critic for Recommender Systems [76.7066594130961]
  本稿では、RL成分を学習するための負のサンプリング戦略を提案し、それを教師付き逐次学習と組み合わせる。 サンプル化された(負の)作用 (items) に基づいて、平均ケース上での正の作用の「アドバンテージ」を計算することができる。 SNQNとSA2Cを4つのシーケンシャルレコメンデーションモデルでインスタンス化し、2つの実世界のデータセットで実験を行う。
  論文  参考訳（メタデータ） (2021-11-05T12:51:15Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
  本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。 T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
  論文  参考訳（メタデータ） (2020-10-05T07:08:26Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。 SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
  論文  参考訳（メタデータ） (2020-07-09T17:08:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。