Reward Augmentation in Reinforcement Learning for Testing Distributed Systems

• URL: http://arxiv.org/abs/2409.02137v1
• Date: Mon, 2 Sep 2024 15:07:05 GMT
• Title: Reward Augmentation in Reinforcement Learning for Testing Distributed Systems
• Authors: Andrea Borgarelli, Constantin Enea, Rupak Majumdar, Srinidhi Nagendra,
• Abstract summary: Bugs in popular distributed protocol implementations have been the source of many downtimes in popular internet services. We describe a randomized testing approach for distributed protocol implementations based on reinforcement learning. We show two different techniques that build on one another.
• Score: 6.0560257343687995
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bugs in popular distributed protocol implementations have been the source of many downtimes in popular internet services. We describe a randomized testing approach for distributed protocol implementations based on reinforcement learning. Since the natural reward structure is very sparse, the key to successful exploration in reinforcement learning is reward augmentation. We show two different techniques that build on one another. First, we provide a decaying exploration bonus based on the discovery of new states -- the reward decays as the same state is visited multiple times. The exploration bonus captures the intuition from coverage-guided fuzzing of prioritizing new coverage points; in contrast to other schemes, we show that taking the maximum of the bonus and the Q-value leads to more effective exploration. Second, we provide waypoints to the algorithm as a sequence of predicates that capture interesting semantic scenarios. Waypoints exploit designer insight about the protocol and guide the exploration to ``interesting'' parts of the state space. Our reward structure ensures that new episodes can reliably get to deep interesting states even without execution caching. We have implemented our algorithm in Go. Our evaluation on three large benchmarks (RedisRaft, Etcd, and RSL) shows that our algorithm can significantly outperform baseline approaches in terms of coverage and bug finding.

Related papers

• STARC: A General Framework For Quantifying Differences Between Reward Functions [55.33869271912095]
  We provide a class of pseudometrics on the space of all reward functions that we call STARC metrics. We show that STARC metrics induce both an upper and a lower bound on worst-case regret. We also identify a number of issues with reward metrics proposed by earlier works.
  arXiv  Detail & Related papers  (2023-09-26T20:31:19Z)
• Flipping Coins to Estimate Pseudocounts for Exploration in Reinforcement Learning [20.0888026410406]
  We show that counts can be derived by averaging samples from the Rademacher distribution. We show that our method is significantly more effective at deducing ground-truth visitation counts than previous work.
  arXiv  Detail & Related papers  (2023-06-05T18:56:48Z)
• Learning in Sparse Rewards settings through Quality-Diversity algorithms [1.4881159885040784]
  This thesis focuses on the problem of sparse rewards with Quality-Diversity (QD) algorithms. The first part of the thesis focuses on learning a representation of the space in which the diversity of the policies is evaluated. The thesis continues with the introduction of the SERENE algorithm, a method that can efficiently focus on the interesting parts of the search space.
  arXiv  Detail & Related papers  (2022-03-02T11:02:34Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  We study the reward-free RL problem, where an agent aims to thoroughly explore the environment without any pre-specified reward function. We tackle this problem under the context of function approximation, leveraging powerful function approximators. We establish the first provably efficient reward-free RL algorithm with kernel and neural function approximators.
  arXiv  Detail & Related papers  (2021-10-19T07:26:33Z)
• MADE: Exploration via Maximizing Deviation from Explored Regions [48.49228309729319]
  In online reinforcement learning (RL), efficient exploration remains challenging in high-dimensional environments with sparse rewards. We propose a new exploration approach via textitmaximizing the deviation of the occupancy of the next policy from the explored regions. Our approach significantly improves sample efficiency over state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-18T17:57:00Z)
• Reannealing of Decaying Exploration Based On Heuristic Measure in Deep Q-Network [82.20059754270302]
  We propose an algorithm based on the idea of reannealing, that aims at encouraging exploration only when it is needed. We perform an illustrative case study showing that it has potential to both accelerate training and obtain a better policy.
  arXiv  Detail & Related papers  (2020-09-29T20:40:00Z)
• Exploring Unknown States with Action Balance [48.330318997735574]
  Exploration is a key problem in reinforcement learning. Next-state bonus methods force the agent to pay overmuch attention in exploring known states. We propose action balance exploration, which balances the frequency of selecting each action at a given state.
  arXiv  Detail & Related papers  (2020-03-10T03:32:28Z)
• Reward-Free Exploration for Reinforcement Learning [82.3300753751066]
  We propose a new "reward-free RL" framework to isolate the challenges of exploration. We give an efficient algorithm that conducts $tildemathcalO(S2Amathrmpoly(H)/epsilon2)$ episodes of exploration. We also give a nearly-matching $Omega(S2AH2/epsilon2)$ lower bound, demonstrating the near-optimality of our algorithm in this setting.
  arXiv  Detail & Related papers  (2020-02-07T14:03:38Z)
• Long-Term Visitation Value for Deep Exploration in Sparse Reward Reinforcement Learning [34.38011902445557]
  Reinforcement learning with sparse rewards is still an open challenge. We present a novel approach that plans exploration actions far into the future by using a long-term visitation count. Contrary to existing methods which use models of reward and dynamics, our approach is off-policy and model-free.
  arXiv  Detail & Related papers  (2020-01-01T01:01:15Z)

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.