42 citations · 185 across the 35 of their papers we have counts for
40 papers
The Complexity of Games with Randomised Control
Sarvin Bahmani, Rasmus Ibsen-Jensen, Soumyajit Paul +5
We study the complexity of solving two-player infinite duration games played on a fixed finite graph, where the control of a node is not predetermined but rather assigned randomly.…
Omega-Regular Decision Processes
Ernst Moritz Hahn, Mateo Perez, Sven Schewe +3
Regular decision processes (RDPs) are a subclass of non-Markovian decision processes where the transition and reward functions are guarded by some regular property of the past (a l…
Omega-Regular Reward Machines
Ernst Moritz Hahn, Mateo Perez, Sven Schewe +3
Reinforcement learning (RL) is a powerful approach for training agents to perform tasks, but designing an appropriate reward mechanism is critical to its success. However, in many…
MC-NN: An End-to-End Multi-Channel Neural Network Approach for Predicting Influenza A Virus Hosts and Antigenic Types
Yanhua Xu, Dominik Wojtczak
Influenza poses a significant threat to public health, particularly among the elderly, young children, and people with underlying dis-eases. The manifestation of severe conditions,…
Multi-channel neural networks for predicting influenza A virus hosts and antigenic types
Yanhua Xu, Dominik Wojtczak
Influenza occurs every season and occasionally causes pandemics. Despite its low mortality rate, influenza is a major public health concern, as it can be complicated by severe dise…
Dive into Machine Learning Algorithms for Influenza Virus Host Prediction with Hemagglutinin Sequences
Yanhua Xu, Dominik Wojtczak
Influenza viruses mutate rapidly and can pose a threat to public health, especially to those in vulnerable groups. Throughout history, influenza A viruses have caused pandemics bet…
Recursive Reinforcement Learning
Ernst Moritz Hahn, Mateo Perez, Sven Schewe +3
Recursion is the fundamental paradigm to finitely describe potentially infinite objects. As state-of-the-art reinforcement learning (RL) algorithms cannot directly reason about rec…
Alternating Good-for-MDP Automata
Ernst Moritz Hahn, Mateo Perez, Sven Schewe +3
When omega-regular objectives were first proposed in model-free reinforcement learning (RL) for controlling MDPs, deterministic Rabin automata were used in an attempt to provide a…
Predicting Influenza A Viral Host Using PSSM and Word Embeddings
Yanhua Xu, Dominik Wojtczak
The rapid mutation of the influenza virus threatens public health. Reassortment among viruses with different hosts can lead to a fatal pandemic. However, it is difficult to detect…
Mungojerrie: Reinforcement Learning of Linear-Time Objectives
Ernst Moritz Hahn, Mateo Perez, Sven Schewe +3
Reinforcement learning synthesizes controllers without prior knowledge of the system. At each timestep, a reward is given. The controllers optimize the discounted sum of these rewa…
Model-free Reinforcement Learning for Branching Markov Decision Processes
Ernst Moritz Hahn, Mateo Perez, Sven Schewe +3
We study reinforcement learning for the optimal control of Branching Markov Decision Processes (BMDPs), a natural extension of (multitype) Branching Markov Chains (BMCs). The state…
Priority Promotion with Parysian Flair
Massimo Benerecetti, Daniele Dell'Erba, Fabio Mogavero +2
We develop an algorithm that combines the advantages of priority promotion - one of the leading approaches to solving large parity games in practice - with the quasi-polynomial tim…
A Recursive Approach to Solving Parity Games in Quasipolynomial Time
Karoliina Lehtinen, Paweł Parys, Sven Schewe +1
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, whil…
Facility Reallocation on the Line
Bart de Keijzer, Dominik Wojtczak
We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between time stages based on the locations reported by agents. The ai…
Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
Richard Mayr, Sven Schewe, Patrick Totzke +1
We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative -regular condition: The maximizer aims to avoid running out of ene…
Satisfiability Modulo Theories and Chiral Heterotic String Vacua with Positive Cosmological Constant
Alon E. Faraggi, Benjamin Percival, Sven Schewe +1
We apply Boolean Satisfiability (SAT) and Satisfiability Modulo Theories (SMT) solvers in the context of finding chiral heterotic string models with positive cosmological constant…
Reward Shaping for Reinforcement Learning with Omega-Regular Objectives
E. M. Hahn, M. Perez, S. Schewe +3
Recently, successful approaches have been made to exploit good-for-MDPs automata (Büchi automata with a restricted form of nondeterminism) for model free reinforcement learning, a…
Good-for-MDPs Automata for Probabilistic Analysis and Reinforcement Learning
Ernst Moritz Hahn, Mateo Perez, Fabio Somenzi +3
We characterize the class of nondeterministic -automata that can be used for the analysis of finite Markov decision processes (MDPs). We call these automata `good-for-MDPs' (GFM…
Coordination Games on Weighted Directed Graphs
Krzysztof R. Apt, Sunil Simon, Dominik Wojtczak
We study strategic games on weighted directed graphs, in which the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy, au…
Open Problems in a Logic of Gossips
Krzysztof R. Apt, Dominik Wojtczak
Gossip protocols are programs used in a setting in which each agent holds a secret and the aim is to reach a situation in which all agents know all secrets. Such protocols rely on…
Improving the complexity of Parys' recursive algorithm
Karoliina Lehtinen, Sven Schewe, Dominik Wojtczak
Parys has recently proposed a quasi-polynomial version of Zielonka's recursive algorithm for solving parity games. In this brief note we suggest a variation of his algorithm that i…
Omega-Regular Objectives in Model-Free Reinforcement Learning
Ernst Moritz Hahn, Mateo Perez, Sven Schewe +3
We provide the first solution for model-free reinforcement learning of ω-regular objectives for Markov decision processes (MDPs). We present a constructive reduction from the almos…
On Strong NP-Completeness of Rational Problems
Dominik Wojtczak
The computational complexity of the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple variants were studied in numero…
Common Knowledge in a Logic of Gossips
Krzysztof R. Apt, Dominik Wojtczak
Gossip protocols aim at arriving, by means of point-to-point or group communications, at a situation in which all the agents know each other secrets. Recently a number of authors s…