Sequential Resource Allocation with situational constraints presents a significant challenge in real-world applications, where resource demands and priorities are context-dependent. This paper introduces a novel framework, SCRL, to address this problem. We formalize situational constraints as logic implications and develop a new algorithm that dynamically penalizes constraint violations. To handle situational constraints effectively, we propose a probabilistic selection mechanism to overcome limitations of traditional constraint reinforcement learning (CRL) approaches. We evaluate SCRL across two scenarios: medical resource allocation during a pandemic and pesticide distribution in agriculture. Experiments demonstrate that SCRL outperforms existing baselines in satisfying constraints while maintaining high resource efficiency, showcasing its potential for real-world, context-sensitive decision-making tasks.

Abstract Lexicographic Ranking SuperMartingale (LexRSM) is a probabilistic extension of Lexicographic Ranking Function (LexRF), which is a widely accepted technique for verifying program termination. In this paper, we are the first to propose sound probabilistic extensions of LexRF with a weaker non-negativity condition, called single-component (SC) non-negativity. It is known that such an extension, if it exists, will be nontrivial due to the intricacies of the probabilistic circumstances. Toward the goal, we first devise the notion of fixability, which offers a systematic approach for analyzing the soundness of possibly negative LexRSM. This notion yields a desired extension of LexRF that is sound for general stochastic processes. We next propose another extension, called Lazy LexRSM, toward the application to automated verification; it is sound over probabilistic programs with linear arithmetics, while its subclass is amenable to automated synthesis via linear programming. We finally propose a LexRSM synthesis algorithm for this subclass, and perform experiments.

The paper introduces two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving Müller games. Müller games constitute a well established class of games in model checking and verification. In connectivity games, the objective of one of the players is to visit every node of the game graph infinitely often. The first contribution of this paper is our proof that solving connectivity games can be reduced to the incremental strongly connected component maintenance (ISCCM) problem, an important problem in graph algorithms and data structures. The second contribution is that we non-trivially adapt two known algorithms for the ISCCM problem to provide two efficient algorithms that solve the connectivity games problem. Finally, based on the techniques developed, we recast Horn’s polynomial time algorithm that solves explicitly given Müller games and provide the first correctness proof of the algorithm. Our algorithms are more efficient than that of Horn’s algorithm. Our solution for connectivity games is used as a subroutine in the algorithm.

Verification of hybrid systems is very challenging, if not impossible, due to their continuous dynamics that leads to infinite state space. As a countermeasure, falsification is usually applied to show that a specification does not hold, by searching for a falsifying input as a counterexample that refutes the specification. A falsification algorithm exploits the quantitative robust semantics of temporal specifications, which provides a numerical robustness that tells how robustly a specification holds or not, and uses it as a guide to explore the input space towards the direction of robustness descent—once negative robustness is observed, it indicates that a falsifying input is found. However, if a falsification algorithm does not return any falsifying input, a user is not sure whether the specification does indeed hold, or there exist counterexamples that the algorithm did not manage to reach. In this case, a measurement on how likely there indeed exists no counterexample in the input space is necessary for better understanding the safety of the system and deciding whether more budget should be allocated for the falsification. To this end, we propose a confidence measure that assesses the likelihood that the system is not falsifiable, i.e., how confident a user should be that a specification holds, given the fact that an algorithm has sampled a set of inputs but did not find any falsifying one. The confidence measure is defined in terms of a coverage criterion of the input space that assesses to which extent the whole input space is explored and a local area is exploited where low robustness is observed. Experiments on commonly-used falsification benchmarks show that our proposed confidence measure is reasonable and can distinguish different specifications.

The difficulty in exploring the game balance has been increasing, especially in Game-as-a-Service (GaaS) with updates in every few weeks, and due to the complexity in game design and business models. In the limited time available for testing, using automated game agents enables much more test plays than using human test players does, and it has been accelerated by the recent progress of deep reinforcement learning. However, understanding specific behaviours of each agent is hard due to their “black-box” nature. In this paper, we propose a method for explaining the behaviour of game agents using differential comparison between agents. This comparison approach is motivated by our experience with existing explanation techniques that often extracted uninteresting, common aspects of the behaviour. In addition, there are large potentials for the application of the comparison: between agents with different learning algorithms, between human agents and automated agents, and between test agents and users. We applied our technique to a prototype of a commercial GaaS and confirmed our technique can extract specific differences between agents.

Abstract The aim of this paper is to shed light on our understanding of large scale properties of infinite strings. We say that one string $\alpha $ has weaker large scale geometry than that of $\beta $ if there is color preserving bi-Lipschitz map from $\alpha $ into $\beta $ with small distortion. This definition allows us to define a partially ordered set of large scale geometries on the classes of all infinite strings. This partial order compares large scale geometries of infinite strings. As such, it presents an algebraic tool for classification of global patterns. We study properties of this partial order. We prove, for instance, that this partial order has a greatest element and also possess infinite chains and antichains. We also investigate the sets of large scale geometries of strings accepted by finite state machines such as Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This connects the work with the complexity theory. We also prove that the quasi-isometry problem is a $\Sigma _2^0$ -complete set, thus providing a bridge with computability theory. Finally, we build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings, thus connecting the topic with algorithmic randomness.

Computing reachability probabilities is a fundamental problem in the analysis of randomized programs. This article aims at a comprehensive and comparative account of various martingale-based methods for over- and under-approximating reachability probabilities. Based on the existing works that stretch across different communities (formal verification, control theory, etc.), we offer a unifying account. In particular, we emphasize the role of order-theoretic fixed points—a classic topic in computer science—in the analysis of randomized programs. This leads us to two new martingale-based techniques, too. We also make an experimental comparison using our implementation of template-based synthesis algorithms for those martingales.

Solving stochastic games with the reachability objective is a fundamental problem, especially in quantitative verification and synthesis. For this purpose, bounded value iteration (BVI) attracts attention as an efficient iterative method. However, BVI’s performance is often impeded by costly end component (EC) computation that is needed to ensure convergence. Our contribution is a novel BVI algorithm that conducts, in addition to local propagation by the Bellman update that is typical of BVI, global propagation of upper bounds that is not hindered by ECs. To conduct global propagation in a computationally tractable manner, we construct a weighted graph and solve the widest path problem in it. Our experiments show the algorithm’s performance advantage over the previous BVI algorithms that rely on EC computation.

We introduce geometric consideration into the theory of formal languages. We aim to shed light on our understanding of global patterns that occur on infinite strings. We utilise methods of geometric group theory. Our emphasis is on large scale geometries. Two infinite strings have the same large scale geometry if there are colour preserving bi-Lipschitz maps with distortions between the strings. Call these maps quasi-isometries. Introduction of large scale geometries poses several questions. The first question asks to study the partial order induced by quasi-isometries. This partial order compares large scale geometries; as such it presents an algebraic tool for classification of global patterns. We prove there is a greatest large scale geometry and infinitely many minimal large scale geometries. The second question is related to understanding the quasi-isometric maps on various classes of strings. The third question investigates the sets of large scale geometries of strings accepted by computational models, e.g. Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This links large scale geometries with automata theory. The fourth question studies the complexity of the quasi-isometry problem. We show the problem is Σ30-complete thus providing a bridge with computability theory. Finally, the fifth question asks to build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings thus connecting the topic with algorithmic randomness.