Automata Learning -- Expect Delays!

• URL: http://arxiv.org/abs/2508.16384v1
• Date: Fri, 22 Aug 2025 13:38:49 GMT
• Title: Automata Learning -- Expect Delays!
• Authors: Gabriel Dengler, Sven Apel, Holger Hermanns,
• Abstract summary: This paper studies active automata learning (AAL) in the presence of delays.<n>We consider Mealy machines that have delays associated with each transition and explore how the learner can efficiently arrive at faithful estimates of those machines.
• Score: 5.208686653449339
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies active automata learning (AAL) in the presence of stochastic delays. We consider Mealy machines that have stochastic delays associated with each transition and explore how the learner can efficiently arrive at faithful estimates of those machines, the precision of which crucially relies on repetitive sampling of transition delays. While it is possible to na\"ively integrate the delay sampling into AAL algorithms such as $L^*$, this leads to considerable oversampling near the root of the state space. We address this problem by separating conceptually the learning of behavior and delays such that the learner uses the information gained while learning the logical behavior to arrive at efficient input sequences for collecting the needed delay samples. We put emphasis on treating cases in which identical input/output behaviors might stem from distinct delay characteristics. Finally, we provide empirical evidence that our method outperforms the na\"ive baseline across a wide range of benchmarks and investigate its applicability in a realistic setting by studying the join order in a relational database.

Related papers

• TempoNet: Slack-Quantized Transformer-Guided Reinforcement Scheduler for Adaptive Deadline-Centric Real-Time Dispatchs [8.818252253980985]
  TempoNet is a reinforcement learning scheduler that pairs a permutation-invariant Transformer with a deep Q-approximation.<n>A latency-aware sparse attention stack with blockwise top-k selection and locality-sensitive chunking enables global reasoning over unordered task sets.
  arXiv  Detail & Related papers  (2026-02-20T09:56:23Z)
• Model-Based Reinforcement Learning under Random Observation Delays [9.860349466867193]
  We study random sensor delays in POMDPs, where observations may arrive out-of-sequence.<n>We propose a model-based filtering process that sequentially updates the belief state based on an incoming stream of observations.<n>We then introduce a simple delay-aware framework that incorporates this idea into model-based RL.
  arXiv  Detail & Related papers  (2025-09-25T08:01:13Z)
• Evaluating the Efficacy of Instance Incremental vs. Batch Learning in Delayed Label Environments: An Empirical Study on Tabular Data Streaming for Fraud Detection [0.13980986259786224]
  In real-world scenarios, such as fraud detection or credit scoring, labels may be delayed. batch incremental algorithms are widely used in many real-world tasks. Our findings indicate that instance incremental learning is not the superior option.
  arXiv  Detail & Related papers  (2024-09-16T09:20:01Z)
• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• DelGrad: Exact event-based gradients for training delays and weights on spiking neuromorphic hardware [1.5226147562426895]
  Spiking neural networks (SNNs) inherently rely on the timing of signals for representing and processing information.<n>We propose DelGrad, an event-based method to compute exact loss gradients for both synaptic weights and delays.<n>We experimentally demonstrate the memory efficiency and accuracy benefits of adding delays to SNNs on noisy mixed-signal hardware.
  arXiv  Detail & Related papers  (2024-04-30T00:02:34Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation [62.969796245827006]
  Delayed-PSVI is an optimistic value-based algorithm that explores the value function space via noise perturbation with posterior sampling. We show our algorithm achieves $widetildeO(sqrtd3H3 T + d2H2 E[tau]$ worst-case regret in the presence of unknown delays. We incorporate a gradient-based approximate sampling scheme via Langevin dynamics for Delayed-LPSVI.
  arXiv  Detail & Related papers  (2023-10-29T06:12:43Z)
• Diffusion Generative Flow Samplers: Improving learning signals through partial trajectory optimization [87.21285093582446]
  Diffusion Generative Flow Samplers (DGFS) is a sampling-based framework where the learning process can be tractably broken down into short partial trajectory segments. Our method takes inspiration from the theory developed for generative flow networks (GFlowNets)
  arXiv  Detail & Related papers  (2023-10-04T09:39:05Z)
• Delayed Reinforcement Learning by Imitation [31.932677462399468]
  We present a novel algorithm that learns how to act in a delayed environment from undelayed demonstrations. We show that DIDA obtains high performances with a remarkable sample efficiency on a variety of tasks.
  arXiv  Detail & Related papers  (2022-05-11T15:27:33Z)
• Delay-adaptive step-sizes for asynchronous learning [8.272788656521415]
  We show that it is possible to use learning rates that depend on the actual time-varying delays in the system. For each of these methods, we demonstrate how delays can be measured on-line, present delay-adaptive step-size policies, and illustrate their theoretical and practical advantages over the state-of-the-art.
  arXiv  Detail & Related papers  (2022-02-17T09:51:22Z)
• A Novel Anomaly Detection Algorithm for Hybrid Production Systems based on Deep Learning and Timed Automata [73.38551379469533]
  DAD:DeepAnomalyDetection is a new approach for automatic model learning and anomaly detection in hybrid production systems. It combines deep learning and timed automata for creating behavioral model from observations. The algorithm has been applied to few data sets including two from real systems and has shown promising results.
  arXiv  Detail & Related papers  (2020-10-29T08:27:43Z)
• Non-Stationary Delayed Bandits with Intermediate Observations [10.538264213183076]
  Online recommender systems often face long delays in receiving feedback, especially when optimizing for some long-term metrics. We introduce the problem of non-stationary, delayed bandits with intermediate observations. We develop an efficient algorithm based on UCRL, and prove sublinear regret guarantees for its performance.
  arXiv  Detail & Related papers  (2020-06-03T09:27:03Z)
• Tracking Performance of Online Stochastic Learners [57.14673504239551]
  Online algorithms are popular in large-scale learning settings due to their ability to compute updates on the fly, without the need to store and process data in large batches. When a constant step-size is used, these algorithms also have the ability to adapt to drifts in problem parameters, such as data or model properties, and track the optimal solution with reasonable accuracy. We establish a link between steady-state performance derived under stationarity assumptions and the tracking performance of online learners under random walk models.
  arXiv  Detail & Related papers  (2020-04-04T14:16:27Z)

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.