Online Test Synthesis From Requirements: Enhancing Reinforcement Learning with Game Theory

• URL: http://arxiv.org/abs/2407.18994v1
• Date: Fri, 26 Jul 2024 07:59:59 GMT
• Title: Online Test Synthesis From Requirements: Enhancing Reinforcement Learning with Game Theory
• Authors: Ocan Sankur, Thierry Jéron, Nicolas Markey, David Mentré, Reiya Noguchi,
• Abstract summary: We consider the automatic online synthesis of black-box test cases from functional requirements specified as automata for reactive implementations. We develop an approach based on Monte Carlo Tree Search, which is a classical technique in reinforcement learning for efficiently selecting promising inputs.
• Score: 1.363146160329157
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the automatic online synthesis of black-box test cases from functional requirements specified as automata for reactive implementations. The goal of the tester is to reach some given state, so as to satisfy a coverage criterion, while monitoring the violation of the requirements. We develop an approach based on Monte Carlo Tree Search, which is a classical technique in reinforcement learning for efficiently selecting promising inputs. Seeing the automata requirements as a game between the implementation and the tester, we develop a heuristic by biasing the search towards inputs that are promising in this game. We experimentally show that our heuristic accelerates the convergence of the Monte Carlo Tree Search algorithm, thus improving the performance of testing.

Related papers

• Adapting Vision-Language Models to Open Classes via Test-Time Prompt Tuning [50.26965628047682]
  Adapting pre-trained models to open classes is a challenging problem in machine learning. In this paper, we consider combining the advantages of both and come up with a test-time prompt tuning approach. Our proposed method outperforms all comparison methods on average considering both base and new classes.
  arXiv  Detail & Related papers  (2024-08-29T12:34:01Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis [0.0]
  We present a reinforcement-learning algorithm for SyGuS which uses Monte-Carlo Tree Search (MCTS) to search the space of candidate solutions. Our algorithm learns policy and value functions which, combined with the upper confidence bound for trees, allow it to balance exploration and exploitation.
  arXiv  Detail & Related papers  (2023-07-13T11:30:50Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• CrossBeam: Learning to Search in Bottom-Up Program Synthesis [51.37514793318815]
  We propose training a neural model to learn a hands-on search policy for bottom-up synthesis. Our approach, called CrossBeam, uses the neural model to choose how to combine previously-explored programs into new programs. We observe that CrossBeam learns to search efficiently, exploring much smaller portions of the program space compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2022-03-20T04:41:05Z)
• Dyna-T: Dyna-Q and Upper Confidence Bounds Applied to Trees [0.9137554315375919]
  We present a preliminary investigation of a novel algorithm called Dyna-T. In reinforcement learning (RL) a planning agent has its own representation of the environment as a model. Experience can be used for learning a better model or improve directly the value function and policy.
  arXiv  Detail & Related papers  (2022-01-12T15:06:30Z)
• MQBench: Towards Reproducible and Deployable Model Quantization Benchmark [53.12623958951738]
  MQBench is a first attempt to evaluate, analyze, and benchmark the and deployability for model quantization algorithms. We choose multiple platforms for real-world deployments, including CPU, GPU, ASIC, DSP, and evaluate extensive state-of-the-art quantization algorithms. We conduct a comprehensive analysis and find considerable intuitive or counter-intuitive insights.
  arXiv  Detail & Related papers  (2021-11-05T23:38:44Z)
• Monte Carlo Tree Search for a single target search game on a 2-D lattice [0.0]
  This project imagines a game in which an AI player searches for a stationary target within a 2-D lattice. We analyze its behavior with different target distributions and compare its efficiency to the Levy Flight Search, a model for animal foraging behavior.
  arXiv  Detail & Related papers  (2020-11-29T01:07:45Z)
• An Efficient Model Inference Algorithm for Learning-based Testing of Reactive Systems [0.0]
  Learning-based testing (LBT) is an emerging methodology to automate iterative black-box requirements testing of software systems. We describe the IKL learning algorithm which is an active incremental learning algorithm for deterministic Kripke structures.
  arXiv  Detail & Related papers  (2020-08-14T09:48:58Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree. How to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. We demonstrate how proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms.
  arXiv  Detail & Related papers  (2020-06-15T21:36:00Z)
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search [8.22379888383833]
  Combination of Monte-Carlo Tree Search (MCTS) and deep reinforcement learning is state-of-the-art in two-player perfect-information games. We describe a search algorithm that uses a variant of MCTS which we enhanced by 1) a novel action value normalization mechanism for games with potentially unbounded rewards, 2) defining a virtual loss function that enables effective search parallelization, and 3) a policy network, trained by generations of self-play, to guide the search.
  arXiv  Detail & Related papers  (2020-05-22T18:02:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.