Search

Markov Decision Processes (MDPs) model systems with uncertain transition dynamics. Multiple-environment MDPs (MEMDPs) extend MDPs. They intuitively reflect finite sets of MDPs that share the same state and action spaces but differ in the transition dynamics. The key objective in MEMDPs is to find a single strategy that satisfies a given objective in every associated MDP. The main result of this paper is PSPACE-completeness for almost-sure Rabin objectives in MEMDPs. This result clarifies the complexity landscape for MEMDPs and contrasts with results for the more general class of partially observable MDPs (POMDPs), where almost-sure reachability is already EXP-complete, and almost-sure Rabin objectives are undecidable.

Delivering after-sales maintenance services is a challenging task for original equipment manufacturers who must tailor their offers to customers’ needs. To accommodate this challenge, we propose a multi-objective optimization model to derive optimal maintenance policies for systems with a large number of heterogeneous components over a finite lifespan. Based on the practical assumption of a fixed time interval between two consecutive scheduled downs, we develop a decomposition approach that enables the fast computation of the optimal policy per component and the optimal time interval between two consecutive scheduled visits. We also analyze the structural properties of the optimal policies for both age-based and condition-based maintenance and prove that they have a non-static control-limit structure. Using a set of computational experiments, we first investigate the computational tractability of our model for systems with an increasing number of components. Then, we apply our model to a real case study to demonstrate how it can be used to derive optimal maintenance policies tailored to different customer needs

In environments like offices, the duration of a robot's navigation between two locations may vary over time. For instance, reaching a kitchen may take more time during lunchtime since the corridors are crowded with people heading the same way. In this work, we address the problem of routing in such environments with tasks expressed in Metric Interval Temporal Logic (MITL)-a rich robot task specification language that allows us to capture explicit time requirements. Our objective is to find a strategy that maximizes the temporal robustness of the robot's MITL task. As the first step towards a solution, we define a Mixed-integer linear programming approach to solving the task planning problem over a Varying Weighted Transition System, where navigation durations are deterministic but vary depending on the time of day. Then, we apply this planner to optimize for MITL temporal robustness in Markov Decision Processes, where the navigation durations between physical locations are uncertain, but the time-dependent distribution over possible delays is known. Finally, we develop a receding horizon planner for Markov Decision Processes that preserves guarantees over MITL temporal robustness. We show the scalability of our planning algorithms in simulations of robotic tasks., Part of ISBN: 9798350384574QC 20240926

We study distributional reachability for finite Markov decision processes (MDPs) from a control theoretical perspective. Unlike standard probabilistic reachability notions, which are defined over MDP states or trajectories, in this paper reachability is formulated over the space of probability distributions. We propose two set-valued maps for the forward and backward distributional reachability problems: the forward map collects all state distributions that can be reached from a set of initial distributions, while the backward map collects all state distributions that can reach a set of final distributions. We show that there exists a maximal invariant set under the forward map and this set is the region where the state distributions eventually always belong to, regardless of the initial state distribution and policy. The backward map provides an alternative way to solve a class of important problems for MDPs: the study of controlled invariance, the characterization of the domain of attraction, and reach-avoid problems. Three case studies illustrate the effectiveness of our approach., QC 20240710

This work studies computation tree logic (CTL) model checking for finite-state Markov decision processes (MDPs) over the space of their distributions. Instead of investigating properties over states of the MDP, as encoded by formulae in standard probabilistic CTL (PCTL), the focus of this work is on the associated transition system, which is induced by the MDP, and on its dynamics over the (transient) MDP distributions. CTL is thus used to specify properties over the space of distributions, and is shown to provide an alternative way to express probabilistic specifications or requirements over the given MDP. We discuss the distinctive semantics of CTL formulae over distribution spaces, compare them to existing non-branching logics that reason on probability distributions, and juxtapose them to traditional PCTL specifications. We then propose reachability-based CTL model checking algorithms over distribution spaces, as well as computationally tractable, sampling-based procedures for computing the relevant reachable sets: it is in particular shown that the satisfaction set of the CTL specification can be soundly under-approximated by the union of convex polytopes. Case studies display the scalability of these procedures to large MDPs., QC 20240612 Part of ISBN 9798400705229

Reinforcement Learning (RL) is a branch of AI that deals with solving complex sequential decision making problems such as training robots, trading while following patterns and trends, optimal control of industrial processes, and more. These applications span various fields, including data science, factories, finance, and others[1]. The most popular RL algorithm today is Deep Q Learning (DQL), developed by a team at DeepMind, which successfully combines RL with Neural Network (NN). However, combining RL and NN introduces challenges such as numerical instability and unstable learning due to high variance. Among others, these issues are due to the“moving target problem”. To mitigate this problem, the target network was introduced as a solution. However, using a target network slows down learning, vastly increases memory requirements, and adds overheads in running the code. In this thesis, we conduct an empirical study to investigate the importance of target networks. We conduct this empirical study for three scenarios. In the first scenario, we train agents in online learning. The aim here is to demonstrate that the target network can be removed after some point in time without negatively affecting performance. To evaluate this scenario, we introduce the concept of the stabilization point. In thesecond scenario, we pre-train agents before continuing to train them in online learning. For this scenario, we demonstrate the redundancy of the target network by showing that it can be completely omitted. In the third scenario, we evaluate a newly developed activation function called Truncated Gaussian Error Linear Unit (TGeLU). For thisscenario, we train an agent in online learning and show that by using TGeLU as anactivation function, we can completely remove the target network. Through the empirical study of these scenarios, we conjecture and verify that a target network has only transient benefits concerning stability. We show that it has no influence on the quality of the

Many real-world problems fall in the category of sequential decision-making under uncertainty; Markov Decision Processes (MDPs) are a common method for modeling such problems. To solve an MDP, one could start from scratch or one could already have an idea of what good policies look like. Furthermore, there could be uncertainty in this idea. In existing literature, a policy search procedure is accelerated by encoding this prior knowledge in an action distribution which is used for policy sampling. Moreover, this is then extended by inferring these action distributions while inferring the policy through Gibbs sampling. Implicitly, this approach assumes a generalization of good and bad actions over the entire state space. This thesis extends the existing method by leveraging a division of the state space into regions and inferring action distributions over these regions, rather than over the entire state space. We show that this can accelerate the policy search. We also show that the algorithm manages to recover if the division is unjustified. The division into regions can hence also be considered a form of prior knowledge of the policy with uncertainty. Finally, inference of the regions themselves is also explored and yields promising results., Computer Science

We consider a multi-task learning problem, where an agent is presented a number of N reinforcement learning tasks. To solve this problem, we are interested in studying the gradient approach, which iteratively updates an estimate of the optimal policy using the gradients of the value functions. The classic policy gradient method, however, may be expensive to implement in the multi-task settings as it requires access to the gradients of all the tasks at every iteration. To circumvent this issue, in this paper we propose to study an incremental policy gradient method, where the agent only uses the gradient of only one task at each iteration. Our main contribution is to provide theoretical results to characterize the performance of the proposed method. In particular, we show that incremental policy gradient methods converge to the optimal value of the multi-task reinforcement learning objectives at a sublinear rate O(1/√k), where k is the number of iterations. To illustrate its performance, we apply the proposed method to solve a simple multi-task variant of GridWorld problems, where an agent seeks to find an policy to navigate effectively in different environments.

There is a large body of work on fixpoint theorems, guaranteeing the existence of fixpoints for certain functions and providing methods for computing them. This includes for instance Banachs’s fixpoint theorem, the well-known result by Knaster-Tarski that is frequently employed in computer science and Kleene iteration. It is less clear how to compute fixpoints if the function whose (least) fixpoint we are interested in is not known exactly, but can only be obtained by a sequence of subsequently better approximations. This scenario occurs for instance in the context of reinforcement learning, where the probabilities of a Markov decision process (MDP) - for which one wants to learn a strategy - are unknown and can only be sampled. There are several solutions to this problem where the fixpoint computation (for determining the value vector and the optimal strategy) and the exploration of the model are interleaved. However, these methods work only well for discounted MDPs, that is in the contractive setting, but not for general MDPs, that is for non-expansive functions. After describing and motivating the problem, we will in particular concentrate on the non-expansive case. There are many interesting systems who value vectors can be obtained by determining the fixpoints of non-expansive functions. Other than contractive functions, they do not guarantee uniqueness of the fixpoint, making it more difficult to approximate the least fixpoint by methods other than Kleene iteration. And also Kleene iteration fails if the function under consideration is only approximated. We hence describe a dampened Mann iteration scheme for (higher-dimensional) functions on the reals that converges to the least fixpoint from everywhere. This scheme can also be adapted to functions that are approximated, under certain conditions. We will in particular study the case of MDPs and consider a related problem that arises when performing model-checking for quantitative mu-calculi, which involves the

This report is concerned with a friendly competition for formal verification and policy synthesis of stochastic models. The main goal of the report is to introduce new benchmarks and their properties within this category and recommend next steps toward next year’s edition of the competition. Given that the tools for stochastic models are at their early stages of development compared to those of non-probabilistic models, the main focus is to report on an initiative to collect a set of minimal benchmarks that all such tools can run, thus facilitating the comparison between the efficiency of the implemented techniques. This friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in Summer 2023.

We study merchant energy production modeled as a compound switching andtiming option. The resulting Markov decision process is intractable. Least squares MonteCarlo combined with information relaxation and duality is a state-of-the-art reinforcementlearning methodology to obtain operating policies and optimality gaps for related models.Pathwise optimization is a competing technique developed for optimal stopping settings,in which it typically provides superior results compared with this approach, albeit with alarger computational effort. We apply these procedures to merchant energy production.Using pathwise optimization requires methodological extensions. We use principal com-ponent analysis and block coordinate descent in novel ways to respectively preconditionand solve the ensuing ill-conditioned and large-scale linear program, which even a cutting-edge commercial solver is unable to handle directly. Both techniques yield near optimaloperating policies on realistic ethanol production instances. However, at the cost of bothconsiderably longer run times and greater memory usage, which limits the number ofstages of the instances that it can handle, pathwise optimization leads to substantially tigh-ter dual bounds compared with least squares Monte Carlo, even when specified in a simplefashion, complementing it in this case. Thus, it plays a critical role in obtaining small opti-mality gaps. Our numerical observations on the magnitudes of these bound improvementsdiffer from what is currently known. This research has potential relevance for other com-modity merchant operations contexts and motivates additional algorithmic work in thearea of pathwise optimization.

We study how to efficiently combine formal methods, Monte Carlo Tree Search (MCTS), and deep learning in order to produce high-quality receding horizon policies in large Markov Decision processes (MDPs). In particular, we use model-checking techniques to guide the MCTS algorithm in order to generate offline samples of high-quality decisions on a representative set of states of the MDP. Those samples can then be used to train a neural network that imitates the policy used to generate them. This neural network can either be used as a guide on a lower-latency MCTS online search, or alternatively be used as a full-fledged policy when minimal latency is required. We use statistical model checking to detect when additional samples are needed and to focus those additional samples on configurations where the learnt neural network policy differs from the (computationally-expensive) offline policy. We illustrate the use of our method on MDPs that model the Frozen Lake and Pac-Man environments ' two popular benchmarks to evaluate reinforcement-learning algorithms., SCOPUS: cp.p, info:eu-repo/semantics/published

This thesis concerns reinforcement learning and dynamical systems in finite discrete problem domains. Artificial intelligence studies through reinforcement learning involves developing models and algorithms for scenarios when there is an agent that is interacting with an environment. By taking actions the agent may induce changes in the observed environment, where a modeled reward system reinforces correct behavior through learning algorithms. Reinforcement learning can be used in a wide variety of different domains, such as finance, robotics, games, routing and health care. However as the subject matures there is an increasing need to more heavily rely on advanced concepts in mathematics and deep learning to further our understanding of existing problems and find new algorithmic insights. Discrete dynamical systems arise in virtually any setting as soon as there is a set of elements subjected to iteration by a defining function. The function may be seen to represent the passing of time or to define the rules for state transitions. If the set of elements is finite but very large then we may find applications in several different fields such as operations research, cryptography and biology, where understanding properties of the structure and long-term behavior without explicit enumeration is key. In Paper I we extend the model of categorical reinforcement learning with a group-aided training procedure involving multiple agents. By having the agents learn through shared distributional information but act independently we argue for an accelerated learning process. We empirically show that the procedure may lead to much more robust learning, stronger individual agent performance and good ensemble efficiency. In Paper II we continue to build upon distributional reinforcement learning for finite Markov processes. A common approach among algorithms is to apply transformations on agent returns for stability and flexibility over a variety of different tasks. We show that o

This paper presents an axiomatic approach to finite Markov decision processes where the discount rate is zero. One of the principal difficulties in the no discounting case is that, even if attention is restricted to stationary policies, a strong overtaking optimal policy need not exists. We provide preference foundations for two criteria that do admit optimal policies: 0-discount optimality and average overtaking optimality. As a corollary of our results, we obtain conditions on a decision maker's preferences which ensure that an optimal policy exists. These results have implications for disciplines where dynamic programming problems arise, including automatic control, dynamic games, and economic development., Validerad;2023;Nivå 2;2023-02-24 (hanlid)

In this thesis, we explore two distinct topics. The first part of the thesis delves into efficient exploration in multi-task bandit models and model-free exploration in large Markov decision processes (MDPs). This section is driven by the recent research community's interest in uncovering optimal methods to navigate complex decision-making problems. In the second part, we examine attack vectors against MDPs and dynamical systems, which is motivated by the research community's recent push to enhance the safety of Machine Learning models against malicious attacks. Additionally, we explore how to quantify uncertainty in an off-policy evaluation problem, reflecting our ongoing efforts to deepen understanding in this domain. In the first part of the thesis, we present an investigation into the sample complexity of identifying the optimal arm in multi-task bandit problems. In this setting, an agent can select a task and efficiently learn through cross-task knowledge transfer. We derive instance-specific lower bounds that any probably approximately correct (PAC) algorithm should satisfy, revealing both theoretically and empirically significant improvements in scaling over previous methods. Subsequently, we investigate model-free exploration in Reinforcement Learning (RL) problems. By leveraging an information-theoretical viewpoint, we focus on the instance-specific lower bound for the number of samples needed to identify a nearly-optimal policy. We develop an approximation of this lower bound involving quantities that can be inferred using model-free approaches. This leads to a new model-free exploration strategy applicable to continuous MDPs. In the second part of the thesis, we begin by investigating two types of attacks on MDPs: those that alter the observations and those that manipulate the control signals of the victim. We present strategies for designing optimal attacks to minimize the collected reward of the victim. Our strategies show how uncertainties induce, I denna avhandling undersöker vi två distinkta ämnen. Den första delen av avhandlingen handlar om effektiv utforskning i multi-uppgift banditmodeller och modellfri utforskning i stora Markov beslutsprocesser (MDP). Detta avsnitt drivs av forskningsvärldens intresse på senaste tiden för att upptäcka optimala metoder för att navigera komplexa beslutsproblem. I den andra delen undersöker vi attackvektorer mot MDP:er och dynamiska system, vilket motiveras av forskningsvärldens senaste satsning på att förbättra säkerheten för maskininlärningsmodeller mot illvilliga attacker. Dessutom utforskar vi hur man kvantifierar osäkerhet i ett off-policy utvärderingsproblem, vilket speglar våra pågående insatser för att fördjupa förståelsen inom detta område.I den första delen av avhandlingen presenterar vi en undersökning av provkomplexiteten vid identifiering av den optimala armen i multi-uppgift banditproblem. I denna miljö kan en agent välja en uppgift och effektivt lära sig genom överföring av kunskap mellan uppgifter. Vi härleder instansspecifika undre gränser som varje sannolikt ungefärligt korrekt (PAC) algoritm bör uppfylla, vilket visar både teoretiskt och empiriskt betydande förbättringar i skalning jämfört med tidigare metoder. Därefter undersöker vi modellfri utforskning i förstärkningsinlärningsproblem (RL). Genom att använda ett informationsteoretiskt perspektiv fokuserar vi på den instansspecifika undre gränsen för det antal prover som behövs för att identifiera en nästan optimal policy. Vi utvecklar en approximation av denna undre gräns med kvantiteter som kan härledas med modellfria metoder. Detta leder till en ny modellfri utforskningsstrategi som är tillämplig på kontinuerliga MDP:er.I den andra delen av avhandlingen börjar vi med att undersöka två typer av attacker på MDP:er: de som ändrar observationerna och de som manipulerar offrets kontrollsignaler. Vi presenterar strategier för att utforma optimala attacker som minimerar den belöning som offret samlar in., QC 20230823

A typical model for real-time status update systems consists of a transmitter node that generates real-time status updates about some physical process(es) of interest and sends them through a communication network to a destination node. Such a model can be used to analyze the performance of a plethora of emerging Internet of Things (IoT)-enabled real-time applications including healthcare, factory automation, autonomous vehicles, and smart homes, to name a few. The performance of these applications highly depends upon the freshness of the information status at the destination node about its monitored physical process(es). Because of that, the main design objective of such real-time status update systems is to ensure timely delivery of status updates from the transmitter node to the destination node. To measure the freshness of information at the destination node, the Age of Information (AoI) has been introduced as a performance metric that accounts for the generation time of each status update (which was ignored by conventional performance metrics, specifically throughput and delay). Since then, there have been two main research directions in the AoI research area. The first direction aimed to analyze/characterize AoI in different queueing-theoretic models/disciplines, and the second direction was focused on the optimization of AoI in different communication systems that deal with time-sensitive information. However, the prior queueing-theoretic analyses of AoI have mostly been limited to the characterization of the average AoI and the prior studies developing AoI/age-aware scheduling/transmission policies have mostly ignored the energy constraints at the transmitter node(s). Motivated by these limitations, this dissertation develops new queueing-theoretic methods that allow the characterization of the distribution of AoI in several classes of status updating systems as well as novel AoI-aware scheduling policies accounting for the energy constraints at the transmit

We consider a Markov decision process for an MX/M/1 queue that is controlled by batches of negative customers. More specifically, we derive conditions that imply threshold-type optimal policies, under either the total discounted cost criterion or the average cost criterion. The performance analysis of the model when it operates under a given threshold-type policy is also studied. We prove a stability condition and a complete stochastic comparison characterization for models operating under different thresholds. Exact and asymptotic results concerning the computation of the stationary distribution of the model are also derived., University of Athens, Depto. de Estadística e Investigación Operativa, Fac. de Ciencias Matemáticas, TRUE, pub

Nondeterministic good-for-MDPs (GFM) automata are for MDP model checking and reinforcement learning what good-for-games automata are for reactive synthesis: a more compact alternative to deterministic automata that displays nondeterminism, but only so much that it can be resolved locally, such that a syntactic product can be analysed. GFM has recently been introduced as a property for reinforcement learning, where the simpler Büchi acceptance conditions it allows to use is key. However, while there are classic and novel techniques to obtain automata that are GFM, there has not been a decision procedure for checking whether or not an automaton is GFM. We show that GFM-ness is decidable and provide an EXPTIME decision procedure as well as a PSPACE-hardness proof.

Problem definition: Bleed–feed is a novel technology that allows biomanufacturers to skip intermediary bioreactor setups. However, the specific time at which bleed–feed is performed is critical for success. The process is stringently regulated, and its implementation involves unique tradeoffs in operational decision making. Our analysis formalizes the operational challenges related to bleed–feed decisions, and our results inform biomanufacturers and policymakers on the potential impact of this technology on current practice. Academic/practical relevance: Operations management (OM) methodologies have not yet been widely adopted in the biomanufacturing industry. This research presents one of the first attempts to demonstrate how OM can complement biomanufacturing to improve operational decisions. We present a practically relevant problem and a rigorous solution approach that is relevant to both OM and biomanufacturing. Methodology: We develop a finite-horizon, discrete-time Markov decision processes model and analyze the structural characteristics of optimal bleed–feed policies. Moreover, we characterize the behavior of the value function as a function of regulatory restrictions. As a salient feature, the MDP model captures both the biological dynamics of fermentation and the operational tradeoffs in biomanufacturing. Results: We show that optimal bleed–feed policies have a three-way control-limit structure under mild conditions that were validated with industry data. Moreover, our analysis reveals that the marginal benefits of bleed–feed diminish as additional bleed–feeds are performed. As a practically relevant benchmark, we consider a risk-averse heuristic and identify sufficient conditions for its optimality. Managerial implications: Our analysis (supported with an industry case study) shows that bleed–feed implementation can provide benefits. Real-world implementation at MSD resulted in an 82.5% improvement in the batch yield per setup (using one bleed–feed). We

Dynamic vehicle routing problems (DVRPs) arise in several applications such as technician routing, meal delivery, and parcel shipping. We consider the DVRP with stochastic customer requests (DVRPSR), in which vehicles must be routed dynamically with the goal of maximizing the number of served requests. We model the DVRPSR as a multi-stage optimization problem, where the first-stage decision defines route plans for serving scheduled requests. Our main contributions are knapsack-based linear models to approximate accurately the expected reward-to-go, measured as the number of accepted requests, at any state of the stochastic system. These approximations are based on representing each vehicle as a knapsack with a capacity given by the remaining service time available along the vehicle’s route. We combine these approximations with optimal acceptance and assignment decision rules and derive efficient and high-performing online scheduling policies. We further leverage good predictions of the expected reward-to-go to design initial route plans that facilitate serving dynamic requests. Computational experiments on very large instances based on a real street network demonstrate the effectiveness of the proposed methods in prescribing high-quality offline route plans and online scheduling decisions.

Kullback–Leibler (KL) control enables efficient numerical methods for nonlinear optimal control problems. The crucial assumption of KL control is the full controllability of transition distributions. However, this assumption is often violated when the dynamics evolves in a continuous space. Consequently, applying KL control to problems with continuous spaces requires some approximation, which leads to the loss of the optimality. To avoid such an approximation, in this paper, we reformulate the KL control problem for continuous spaces so that it does not require unrealistic assumptions. The key difference between the original and reformulated KL control is that the former measures the control effort by the KL divergence between controlled and uncontrolled transition distributions while the latter replaces the uncontrolled transition by a noise-driven transition. We show that the reformulated KL control admits efficient numerical algorithms like the original one without unreasonable assumptions. Specifically, the associated value function can be computed by using a Monte Carlo method based on its path integral representation.

Model-Based Reinforcement Learning (MBRL) algorithms solve sequential decision-making problems, usually formalised as Markov Decision Processes, using a model of the environment dynamics to compute the optimal policy. When dealing with complex environments, the environment dynamics are frequently approximated with function approximators (such as Neural Netoworks) that are not guaranteed to converge to an optimal solution. As a consequence, the planning process using samples generated by an imperfect model is also not guaranteed to converge to the optimal policy. In fact, the mismatch between source and target dynamics distribution can result in compounding errors, leading to poor algorithm performance during testing. To mitigate this, we combine the Robust Markov Decision Processes (RMDPs) framework and an ensemble of models to take into account the uncertainty in the approximation of the dynamics. With RMDPs, we can study the uncertainty problem as a two-player stochastic game where Player 1 aims to maximize the expected return and Player 2 wants to minimize it. Using an ensemble of models, Player 2 can choose the worst model to carry out the transitions when performing rollout for the policy improvement. We experimentally show that finding a maximin strategy for this game results in a policy robust to model errors leading to better performance when compared to assuming the learned dynamics to be correct., Computer Science | Data Science and Technology

This article studies the optimal control of batching equipment in the poultry processing industry. The problem is to determine a control policy that maximizes the long-term average revenue while achieving a target throughput. This problem is formulated as a Markov Decision Process (MDP). The developed MDP model captures the unique characteristics of poultry processing operations, such as, the trade-off between giveaway and throughput. Structural properties of the optimal policy are derived for small-sized problems where batching equipment utilizes a single bin. Since the MDP model is numerically intractable for industry-sized problems, we propose a heuristic index policy with a Dynamic Rejection Threshold (DRT). The DRT heuristic is constructed based on the salient characteristics of the problem setting and is easy to implement in practice. Numerical experiments demonstrate that DRT performs well. We present an industry case study where DRT is benchmarked against current practice, which shows that the expected revenue can be potentially increased by over 2% (yielding an additional revenue between 750,000 and 2,270,000 Euros per year) through the use of DRT.

We consider the framework of transfer-entropy-regularized Markov Decision Process (TERMDP) in which the weighted sum of the classical state-dependent cost and the transfer entropy from the state random process to the control input process is minimized. Although TERMDPs are generally formulated as nonconvex optimization problems, an analytical necessary optimality condition can be expressed as a finite set of nonlinear equations, based on which an iterative forward-backward computational procedure similar to the Arimoto-Blahut algorithm is developed. It is shown that every limit point of the sequence generated by the proposed algorithm is a stationary point of the TERMDP. Applications of TERMDPs are discussed in the context of networked control systems theory and non-equilibrium thermodynamics. The proposed algorithm is applied to an information-constrained maze navigation problem, whereby we study how the price of information qualitatively alters the optimal decision polices., QC 20220215

We present a system for interactive examination of learned security policies. It allows a user to traverse episodes of Markov decision processes in a controlled manner and to track the actions triggered by security policies. Similar to a software debugger, a user can continue or or halt an episode at any time step and inspect parameters and probability distributions of interest. The system enables insight into the structure of a given policy and in the behavior of a policy in edge cases. We demonstrate the system with a network intrusion use case. We examine the evolution of an IT infrastructure's state and the actions prescribed by security policies while an attack occurs. The policies for the demonstration have been obtained through a reinforcement learning approach that includes a simulation system where policies are incrementally learned and an emulation system that produces statistics that drive the simulation runs., QC 20220926Part of proceedings: ISBN 978-1-6654-0601-7

This thesis explores the intersection between planning and learning methods for autonomous sequential decision-making. Planning is a model-based approach to autonomous sequential decision-making where action policies are derived automatically through a model of an environment. Alternatively, learning methods learn action policies through interaction with an environment. The planning and learning approaches can be likened to current theories of human cognition which propose a fast and associative system works in conjunction with a slow and deliberative one. From this observation previous work has conjectured that in order to create intelligent systems that are more general and robust than existing ones, a combination of planning and learning methods may be required. Two common high-level approaches for combining planning and learning are to use learning to help guide the search effort of planners and to use planners to teach learning algorithms. This thesis examines these two high-level approaches through the topics of cost-to-go approximations, symbolic regression and imitation. We propose and study a number of new algorithms which provide new insights into methods that combine planning and learning, namely, we introduce methods for learning value and policy functions from lookeaheads; learning from single demonstrations produced by planners; and learning heuristics for planning algorithms.

Two-player (antagonistic) games on (possibly stochastic) graphs are a prevalent model in theoretical computer science, notably as a framework for reactive synthesis. Optimal strategies may require randomisation when dealing with inherently probabilistic goals, balancing multiple objectives, or in contexts of partial information. There is no unique way to define randomised strategies. For instance, one can use so-called mixed strategies or behavioural ones. In the most general settings, these two classes do not share the same expressiveness. A seminal result in game theory - Kuhn’s theorem - asserts their equivalence in games of perfect recall. This result crucially relies on the possibility for strategies to use infinite memory, i.e., unlimited knowledge of all past observations. However, computer systems are finite in practice. Hence it is pertinent to restrict our attention to finite-memory strategies, defined as automata with outputs. Randomisation can be implemented in these in different ways: the initialisation, outputs or transitions can be randomised or deterministic respectively. Depending on which aspects are randomised, the expressiveness of the corresponding class of finite-memory strategies differs. In this work, we study two-player turn-based stochastic games and provide a complete taxonomy of the classes of finite-memory strategies obtained by varying which of the three aforementioned components are randomised. Our taxonomy holds both in settings of perfect and imperfect information, and in games with more than two players.

Although the notion of task similarity is potentially interesting in a wide range of areas such as curriculum learning or automated planning, it has mostly been tied to transfer learning. Transfer is based on the idea of reusing the knowledge acquired in the learning of a set of source tasks to a new learning process in a target task, assuming that the target and source tasks are close enough. In recent years, transfer learning has succeeded in making reinforcement learning (RL) algorithms more efficient (e.g., by reducing the number of samples needed to achieve (near-)optimal performance). Transfer in RL is based on the core concept of similarity: whenever the tasks are similar, the transferred knowledge can be reused to solve the target task and significantly improve the learning performance. Therefore, the selection of good metrics to measure these similarities is a critical aspect when building transfer RL algorithms, especially when this knowledge is transferred from simulation to the real world. In the literature, there are many metrics to measure the similarity between MDPs, hence, many definitions of similarity or its complement distance have been considered. In this paper, we propose a categorization of these metrics and analyze the definitions of similarity proposed so far, taking into account such categorization. We also follow this taxonomy to survey the existing literature, as well as suggesting future directions for the construction of new metrics

This paper develops and analyzes a Markov chain model for the treatment of cancer. Cancer therapy is modeled as the patient's Markov Decision Problem, with the objective of maximizing the patient's discounted expected quality of life years. Patients make decisions on the duration of therapy based on the progression of the disease as well as their own preferences. We obtain a powerful analytic decision tool through which patients may select their preferred treatment strategy. We illustrate the tradeoffs patients in a numerical example and calculate the value lost to a cohort in suboptimal strategies. In a second model patients may make choices to include drug holidays. By delaying therapy, the patient temporarily forgoes the gains of therapy in order to delay its side effects. We obtain an analytic tool that allows numerical approximations of the optimal times of delay., Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Mathematical Physics

Overdiagnosis of breast cancer, defined as diagnosing a cancer that would otherwise not cause symptoms or death in a patient's lifetime, costs U.S. health care system over $1.2 billion annually. Overdiagnosis rates, estimated to be around 10%-40%, may be reduced if indolent breast findings can be identified and followed with noninvasive imaging rather than biopsy. However, there are no validated guidelines for radiologists to decide when to choose imaging options recognizing cancer grades and types. The aim of this study is to optimize breast cancer diagnostic decisions based on cancer types using a large-scale finite-horizon Markov decision process (MDP) model with 4.6 million states to help reduce overdiagnosis. We prove the optimality of a divide-and-search algorithm that relies on tight upper bounds on the optimal decision thresholds to find an exact optimal solution. We project the high-dimensional MDP onto two lower dimensional MDPs and obtain feasible upper bounds on the optimal decision thresholds. We use real data from two private mammography databases and demonstrate our model performance through a previously validated simulation model that has been used by the policy makers to set the national screening guidelines in the United States. We find that a decision-analytical framework optimizing diagnostic decisions while accounting for breast cancer types has a strong potential to improve the quality of life and alleviate the immense costs of overdiagnosis. Our model leads to a 20%$20\%$ reduction in overdiagnosis on the screening population, which translates into an annual savings of approximately $300 million for the U.S. health care system.

In this study, the potential of using Reinforcement Learning for Portfolio Optimization is investigated, considering the constraints set by the stock market, such as liquidity, slippage, and transaction costs. Five Deep Reinforcement Learning (DRL) agents are trained in two different environments to test the agents' ability to learn the best trading strategies to allocate assets, expecting to generate higher cumulative returns. All agents used are model-free and already optimized for financial problems, using the FinRL library. Therefore, the state-space has a high dimension, as found in the financial market environments. The two proposed environments use market data from US stocks, and one of them also uses Finsent data, an alternative data source that contains the news sentiment for all the stocks that are part of Dow Jones Industrial Average (DJIA). A series of backtesting experiments were performed from the beginning of 2019 to the beginning of 2020 and compared the two environments and how the agents performed against the DJIA. All the results were assessed with the pyfolio Python library, which uses all standard metrics to evaluate portfolio performance. Some algorithms increased the cumulative returns compared to the first dataset. The best result obtained outperformed DJIA by a significant amount and a smaller drawdown.

This report presents the results of a friendly competition for formal verification and policy synthesis of stochastic models. It also introduces new benchmarks and their properties within this category and recommends next steps for this category towards next year’s edition of the competition. In comparison with tools on non-probabilistic models, the tools for stochastic models are at the early stages of development that do not allow full competition on a standard set of benchmarks. We report on an initiative to collect a set of minimal benchmarks that all such tools can run, thus facilitating the comparison between efficiency of the implemented techniques. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in Summer 2022.

Sequential decision-making under uncertainty is an important branch of artificial intelligence research with a plethora of real-life applications. In this thesis, we generalize two fundamental properties of the decision-making process. First, we show that the theory on planning methods for finite spaces can be extended to infinite but countable spaces. Second, we propose a unified model of reinforcement learning algorithms that employ the principle of optimism in the face of uncertainty. This model is used to explain why these methods are efficient. We use the developed theory to design novel algorithms. Depending on the user's needs, these algorithms can either automate the decision-making process completely, or provide advice in decision-support systems. We start with presenting the basic concepts from the theory of decision-making and discuss the two approaches to it: planning and reinforcement learning. We look at a few typical sequential decision-making problems of increasing difficulty. In particular, we present a game that involves grid navigation and the problems of warehouse management and wind farm operation. Next, we survey the state-of-the-art methods for solving such problems. Based on this analysis, we identify the following research opportunities. In planning, models with non-stationary and countably-infinite data remain relatively untreated because they are equivalent to infinitely-dimensional optimization problems, which are notoriously difficult to solve even approximately. In reinforcement learning, optimistic approaches lead to computational efficiency, yet the theory of optimism remains undeveloped. Moreover, while reinforcement learning shines at playing games, such as chess, shōgi, Go, and StarCraft II, its practical applications remain few. Next, we overview a mathematical framework of sequential decision-making under uncertainty known as the Markov decision process. We explain how the goal of the decision-maker can, Algorithmics

A labelled Markov decision process (MDP) is a labelled Markov chain with nondeterminism; i.e., together with a strategy a labelled MDP induces a labelled Markov chain. Motivated by applications to the verification of probabilistic noninterference in security, we study problems whether there exist strategies such that the labelled MDPs become bisimilarity equivalent/inequivalent. We show that the equivalence problem is decidable; in fact, it is EXPTIME-complete and becomes NP-complete if one of the MDPs is a Markov chain. Concerning the inequivalence problem, we show that (1) it is decidable in polynomial time; (2) if there are strategies for inequivalence then there are memoryless strategies for inequivalence; (3) such memoryless strategies can be computed in polynomial time.

In this paper, we consider a problem of packet scheduling in the setting of remote estimation with usage-dependent Markovian packet losses. A sensor measures the state of a discrete-time linear process, computes the estimate via a local Kalman filter, and sends the packets to a remote estimator via a network. The link state evolves as a two-state Markov chain, and its state transition depends on the network usage. The aim is to design the scheduling policy which balances the estimation quality and the energy consumption. We identify the problem as a Markov decision process (MDP) and prove the structural properties of the optimal policy. Furthermore, based on the structural properties, we derive the sufficient and necessary condition of the mean square stability of the remote estimator. Simulation examples are provided to illustrate the results. © 2020 Elsevier Ltd

Transitioning to use automated vehicles is a gradual process. Until full automation capabilities are developed there is a need to mediate which driving entity - human or autonomous driving system (ADS) - should be in control depending on the circumstances. This research aims at investigating the switching between manual and automated driving in semi-autonomous vehicles when the ADS becomes unfit to drive. To this end, a simple environment simulation was created and an MDP model was formulated that accounts for sensor failures and leaving the operational design domain (ODD). Deep Q-Network (DQN), a deep reinforcement learning (RL) algorithm was trained and evaluated against a hand-curated decision-tree-based standard. The DQN-based policy did not reach the performance of the baseline algorithm. The conclusion is drawn that using DQN to handle this multi-objective decision problem using an intuition-based reward function cannot learn an optimal policy., CSE3000 Research Project, Computer Science and Engineering

Multi-robot systems are being increasingly deployed to solve real-world problems, from warehouses to autonomous fleets for logistics, from hospitals to nuclear power plants and emergency search and rescue scenarios. These systems often need to operate in uncertain environments which can lead to robot failure, uncertain action durations or the inability to complete assigned tasks. In many scenarios, the safety or reliability of these systems is critical to their deployment. Therefore there is a need for robust multi-robot planning solutions that offer guarantees on the performance of the robot team. In this thesis we develop techniques for robust multi-robot task allocation and planning under uncertainty by building on techniques from formal verification. We present three algorithms that solve the problem of task allocation and planning for a multi-robot team operating under uncertainty. These algorithms are able to calculate the expected maximum number of tasks the multi-robot team can achieve, considering the possibility of robot failure. They are also able to reallocate tasks when robots fail. We formalise the problem of task allocation and robust planning for a multi-robot team using Linear Temporal Logic to specify the team's mission and Markov decision processes to model the robots. Our first solution method is a sampling based approach to simultaneous task allocation and planning. Our second solution method separates task allocation and planning for the same problem using auctioning for the former. Our final solution lies midway between the first two using simultaneous task allocation and planning in a sequential team model. We evaluate all solution approaches extensively using a set of tests inspired by existing benchmarks in related fields.%with a focus on scalability.

In this paper we provide new randomized algorithms with improved runtimes for solving linear programs with two-sided constraints. In the special case of the minimum cost flow problem on n-vertex m-edge graphs with integer polynomially-bounded costs and capacities we obtain a randomized method which solves the problem in O(m + n1.5) time. This improves upon the previous best runtime of O(m ?n) [Lee-Sidford'14] and, in the special case of unit-capacity maximum flow, improves upon the previous best runtimes of m4/3 + o(1) [Liu-Sidford'20, Kathuria'20] and O(m ?n) [Lee-Sidford'14] for sufficiently dense graphs. In the case of ?1-regression in a matrix with n-columns and m-rows we obtain a randomized method which computes an ?-approximate solution in O(mn + n2.5) time. This yields a randomized method which computes an ?-optimal policy of a discounted Markov Decision Process with S states and, A actions per state in time O(S2 A + S2.5). These methods improve upon the previous best runtimes of methods which depend polylogarithmically on problem parameters, which were O(mn1.5) [Lee-Sidford'15] and O(S2.5 A) [Lee-Sidford'14, Sidford-Wang-Wu-Ye'18] respectively. To obtain this result we introduce two new algorithmic tools of possible independent interest. First, we design a new general interior point method for solving linear programs with two sided constraints which combines techniques from [Lee-Song-Zhang'19, Brand et al.'20] to obtain a robust stochastic method with iteration count nearly the square root of the smaller dimension. Second, to implement this method we provide dynamic data structures for efficiently maintaining approximations to variants of Lewis-weights, a fundamental importance measure for matrices which generalize leverage scores and effective resistances., Part of proceedings: ISBN 978-1-4503-8053-9QC 20220321

In this study, we present a meta-learning model to adapt the predictions of the network's capacity between viewers who participate in a live video streaming event. We propose the MELANIE model, where an event is formulated as a Markov Decision Process, performing meta-learning on reinforcement learning tasks. By considering a new event as a task, we design an actor-critic learning scheme to compute the optimal policy on estimating the viewers' high-bandwidth connections. To ensure fast adaptation to new connections or changes among viewers during an event, we implement a prioritized replay memory buffer based on the Kullback-Leibler divergence of the reward/throughput of the viewers' connections. Moreover, we adopt a model-agnostic meta-learning framework to generate a global model from past events. As viewers scarcely participate in several events, the challenge resides on how to account for the low structural similarity of different events. To combat this issue, we design a graph signature buffer to calculate the structural similarities of several streaming events and adjust the training of the global model accordingly. We evaluate the proposed model on the link weight prediction task on three real-world datasets of live video streaming events. Our experiments demonstrate the effectiveness of our proposed model, with an average relative gain of 25% against state-of-the-art strategies. For reproduction purposes, our evaluation datasets and implementation are publicly available at https://github.com/stefanosantaris/melanie, Part of ISBN 9781450391283QC 20220822

We study automated intrusion prevention using reinforcement learning. In a novel approach, we formulate the problem of intrusion prevention as an optimal stopping problem. This formulation allows us insight into the structure of the optimal policies, which turn out to be threshold based. Since the computation of the optimal defender policy using dynamic programming is not feasible for practical cases, we approximate the optimal policy through reinforcement learning in a simulation environment. To define the dynamics of the simulation, we emulate the target infrastructure and collect measurements. Our evaluations show that the learned policies are close to optimal and that they indeed can be expressed using thresholds., Part of proceedings: ISBN 978-3-903176-36-2, QC 20220830