# Omega-Regular Reward Machines

Ernst Moritz Hahn  University of TwenteTwenteThe Netherlands
<EMAIL_ADDRESS>0000-0002-9348-7684 ,  Mateo Perez  University of Colorado
BoulderBoulderColorado80309USA<EMAIL_ADDRESS>0000-0003-4220-3212 ,
Sven Schewe  University of LiverpoolAshton Building, Ashton
StreetLiverpoolEnglandL69 3BXUK<EMAIL_ADDRESS>0000-0002-9093-9518 ,  Fabio Somenzi  University of Colorado
BoulderBoulderColorado80309USA<EMAIL_ADDRESS>0000-0002-2085-2003 ,
Ashutosh Trivedi  University of Colorado BoulderBoulderColorado80309USA
<EMAIL_ADDRESS>0000-0001-9346-0126 and  Dominik Wojtczak
University of LiverpoolAshton Building, Ashton StreetLiverpoolEnglandL69 3BXUK
<EMAIL_ADDRESS>0000-0001-5560-0546

(2023)

###### Abstract.

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 cases, the complexity of the learning objectives
goes beyond the capabilities of the Markovian assumption, necessitating a more
sophisticated reward mechanism. Reward machines and $\omega$-regular languages
are two formalisms used to express non-Markovian rewards for quantitative and
qualitative objectives, respectively. This paper introduces $\omega$-regular
reward machines, which integrate reward machines with $\omega$-regular
languages to enable an expressive and effective reward mechanism for RL. We
present a model-free RL algorithm to compute $\varepsilon$-optimal strategies
against $\omega$-regular reward machines and evaluate the effectiveness of the
proposed algorithm through experiments.

††copyright: rightsretained††journalyear: 2023††doi: ††journal: JACM††ccs:
Theory of computation Automata over infinite objects††ccs: Computing
methodologies Machine learning algorithms††ccs: Mathematics of computing
Markov processes††ccs: Theory of computation Convergence and learning in games

##  1\. Introduction

Reinforcement learning (RL) (Sutton and Barto, 2018) is a powerful learning-
based synthesis paradigm that relies on providing rewards and punishment
signals to reinforce or diminish behaviours. This is based on the principle
that behaviours that are repeatedly rewarded tend to become habitual, while
behaviours that are punished tend to diminish with experience. Therefore,
translating high-level objectives into reward and punishment signals is
critical to successful RL applications.

Simple objectives, such as cost-optimal reachability or safety, can be
intuitively encoded into Markovian reward signals. However, more complex
objectives require a stateful reward mechanism. Two formalisms that have been
used to express non-Markovian reward signals are formal specifications
($\omega$-regular languages and linear temporal logic)(Sadigh et al., 2014;
Hahn et al., 2019; Camacho et al., 2019; Gaon and Brafman, 2020) and reward
machines (Mealy machines based monitors with scalar rewards as outputs)(Icarte
et al., 2018; Camacho et al., 2018). The former is used to express long-run
logical constraints, or “qualitative” specifications, while the latter is used
for “quantitative” objectives, such as the discounted sum of rewards. Note
that the terms _qualitative_ and _quantitative_ are used in this paper to
differentiate between logic-based specifications over infinite behaviour and
reward-based optimisation objectives. However, it’s important to note that
these terms can be misleading since maximising the probability of satisfying a
logical property is technically a quantitative requirement. Similarly, finding
a policy that provides a reward greater than a given budget can be considered
a qualitative requirement.

This paper argues for the need to optimise quantitative rewards under logical
constraints over infinite horizons and proposes a model to conveniently
express such learning objectives, which we refer to as _$\omega$ -regular
reward machines_. These models integrate the two formalisms, allowing for the
optimisation of quantitative rewards while also enforcing logical constraints
over infinite horizons. The proposed $\omega$-regular reward machines provide
a powerful and efficient way to specify complex reward structures for RL,
enabling the effective and efficient training of RL agents.

###  1.1. Reward Programming in RL

Formal specifications, such as linear temporal logic (LTL), $\omega$-regular
languages, and their generalisations (Baier and Katoen, 2008), provide
unambiguous and intuitive languages to express infinite-horizon requirements.
However, manually designing rewards from higher-level specifications is
tedious and error-prone. To address this challenge, researchers have proposed
automatic translations from formal specifications to reward signals, providing
a programmable, transparent, explainable, and trustworthy RL.

Sadigh et al. (Sadigh et al., 2014) initiated the study of model-free RL,
where learning objectives were expressed in LTL. They used LTL to
$\omega$-automaton reduction (Baier and Katoen, 2008) to design a scalar
reward signal, with the hope that maximising the discounted objective
maximises the probability of satisfaction of the LTL objective. However, the
work of Hahn _et al._ (Hahn et al., 2019) revealed challenges in translating
formal specifications to reward machines, and proposed a correct translation
from more general $\omega$-automata based requirements to reward machines.
Since then, several formally correct reward schemes (Hahn et al., 2020b, a;
Bozkurt et al., 2020; Oura et al., 2020) have been proposed to automate
$\omega$-regular reward translation.

Icarte et al. (Icarte et al., 2018, 2022) advocated for the need of non-
Markovian reward signals and popularised the use of Mealy machines to express
such rewards. Reward machines provide an imperative language to program reward
signals, allowing designers to better tune the reward logic by expressing
their domain-specific expertise in the form of scalar rewards. However, we
argue that—since reward machines encode a finite-horizon, albeit discounted,
view of the environment—they fail to capture intuitive specifications and give
rise to unintended and undesirable behaviours. To support this claim, we adapt
the counterexample given by Hahn et al. (Hahn et al., 2019) for the
translation scheme of Sadigh et al. (Sadigh et al., 2014) to show how reward
machines fail to capture intuitive specifications.

$q_{0}$$q_{1}$$q_{2}$$q_{3}$$q_{4}$$\neg A$$A$$\neg B$$B$$\neg C$$C$$\neg
D$$D$$\text{true},+1$

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$0$$1$$2$$3$$4$$5$$6$$7$$8$$A$$B$$C$$D$

Figure 1. An $\omega$-regular reward machine and the corresponding learned
strategy in the office patrol example. The arrow colour corresponds to the
$\omega$-regular reward machine state colours. The strategy was learned with
Q-learning, as described in Section 4. Rewards are zero unless otherwise
specified.

###### Example 1.1 (Counter-intuitive Office Grid-World.).

Figure 1 shows a grid-world example adapted from (Icarte et al., 2022). A
robot patrols the four corner rooms of an office complex. However, unlike in
(Icarte et al., 2022), an electrical wire dangles from the ceiling along the
path connecting rooms $A$ and $B$, blocking safe passage. The robot can avoid
the hazard by reaching $B$ from $A$ via $D$ and $C$ and then retracing its
steps. Alternatively, it can try to fix the dangling wire but, in so doing, it
may be damaged and put out of commission with probability $1/5$. If
successful, the robot can then follow the shorter route that connects the
corners in a simple cycle. Doling out reward every time the robot completes
one round does not guarantee that the robot will follow the _safe_ strategy
that avoids the dangling wire. This is because the _risky_ strategy, where the
robot attempts to fix the dangling wire, incurs a risk that is offset by the
reduction in path length, resulting in a higher expected discounted reward.
The key problem is that maximising the expectation of the cumulative reward is
different from maximising the probability that the reward is positive. We
transform the reward machine into an $\omega$-regular reward machine by
marking the state $q_{4}$ as _accepting_ (or, equivalently, mark its outgoing
transitions as accepting). The overall objective is now modified so that
visiting this accepting state infinitely with maximum probability takes
precedence over the discounted reward. Using the technique described in this
paper, we learn a strategy with Q-learning that satisfies the $\omega$-regular
reward machine and patrols while avoiding the hazard.

At the same time, $\omega$-regular language-based RL is not sufficient to
express simple quantitative preferences as shown in the following example.

###### Example 1.2 (Office Grid-World with Preference.).

In the environment of Figure 1, the robot may be tasked with picking up mail
and coffee for the people who work in the “office” room. The robot may be free
to collect the mail before getting the coffee, or vice versa but, _preferably_
it should get mail first to prevent the coffee from getting cold. This kind of
preference is naturally expressed as rewards on the transitions of the reward
machine, while the satisfaction of the main objective (delivery of mail and
coffee to the office) is guaranteed by imposing an $\omega$-regular objective.

While there are some efforts to combine quantitative and qualitative formalism
to express learning objective, they have been limited in expressing
$\omega$-regular languages (Icarte et al., 2018, 2022; Bozkurt et al., 2021).
To the best of our knowledge, there is no prior work that can handle general
$\omega$-regular objectives with discounted rewards. We propose
$\omega$-regular reward machines to fill this gap. The $\omega$-regular reward
machines ($\omega$-RMs) are defined as nondeterministic Büchi automata
equipped with a scalar reward function. In RL, $\omega$-RMs can act as
interpreters that observe the sequence of actions taken by the learning agent
and the corresponding sequence of observations from the environment and
provide a sequence of scalar rewards. Unlike reward machines (Icarte et al.,
2022), $\omega$-RMs may be non-deterministic, and the resolution of these
choices is delegated to the RL agent. The goal of the RL agent is primarily to
visit the accepting states infinitely often and then maximise the discounted
sum of rewards. Besides the examples above, there are multiple scenarios that
call for expressing such combinations in RL.

  * •

Specification gaming. The term _specification gaming_ refers to the behaviour
of a learning agent that satisfies the literal specification, often in the
terms of the reward signal, but not the intended one. While it is impossible
to eliminate instances of specification gaming beforehand, detecting such
behaviour can provide clues to some underspecified constraints.

Although it is easy to explicitly express the constraints, designing reward
signals that integrate such constraints can be challenging. For instance,
consider the coastrunner example described in (Clark and Amodei, 2016). The
environment provides a positive reward for target hitting, assuming that the
agent naturally wants to finish the boat race as soon as possible. However,
since this assumption is not backed by any explicit reinforcement, the learned
behavior may not align with the desired one. One possible reward mechanism to
address this issue is $\omega$-regular reward machines that provide the
discounted sum of rewards predicated upon the satisfaction of the
$\omega$-regular objective that the agent eventually terminates the boat race.
Note that this requirement cannot be expressed directly as a reward machine or
in formal logic.

  * •

Relative Preference over Accepting States. Büchi automata (Baier and Katoen,
2008) generalise finite automata to accept infinite behaviours that cause the
accepting transitions to be visited infinitely often. $\omega$-regular reward
machines generalise Büchi automata by allowing the designer to express
relative preference over various accepting states.

  * •

Repair Machines. Another scenario where $\omega$-regular reward machines can
be useful is in repair machines. Suppose we have an RL problem where the
learning objective is expressed as a Büchi automaton, and the RL agent can
rewrite some of the observations of the environment before they are evaluated
by the interpreter. The space of these repairs is given by a repair machine
(Dave et al., 2022), which is defined as a weighted nondeterministic
transducer, where the weight corresponds to the cost of the rewrite action. In
this case, the goal of the RL agent is to satisfy the objective given by the
Büchi automaton while minimising a discounted sum of the costs associated with
the repairs. The composition of the Büchi automaton-based specification and
the repair machine can be expressed as an $\omega$-regular reward machines. By
leveraging $\omega$-regular reward machines, we can ensure that the learning
agent satisfies the intended specifications while optimising the cumulative
reward and minimising the costs associated with the repairs.

  * •

Ulysses Contract. Another application of $\omega$-regular reward machines is
in modelling Ulysses contracts. A Ulysses contract is a decision made by an
agent to restrict potentially tempting but irrational choices by a future
version of itself. This form of self-binding contract is named after the Greek
hero Ulysses who, in the Odyssey, has his crew tie him to the mast to safely
enjoy the sirens’ song. With $\omega$-regular RMs, the requirement to visit
certain states infinitely often encodes the Ulysses contract, while the
individual rewards encode various immediate rewards. This model allows the RL
agent to maximise rewards without violating the specification. By using
$\omega$-regular reward machines to express Ulysses contracts, we can ensure
that the learning agent follows a long-term plan of action that aligns with
the desired objectives, even in the presence of potentially tempting but
irrational choices.

###  1.2. Contributions

The paper provides an expressive framework for designing RL agents that can
satisfy complex temporal specifications while optimising the cumulative
reward. We introduce $\omega$-regular reward machines, which can express
complex objectives involving both quantitative and qualitative aspects. We
then provide a convergent RL algorithm that approximates the optimal value for
the $\omega$-regular objective. In the case of a known model, we show the
tractability of computing optimal value and $\varepsilon$-optimal policies. We
also implement the proposed algorithm as an open-source tool and provide
experimental results demonstrating its effectiveness.

###  1.3. Related Work

So far, we have cited several related works on reward machines (Icarte et al.,
2018, 2022) and formal specifications (Sadigh et al., 2014; Hasanbeig et al.,
2019; Hahn et al., 2019, 2020b; Oura et al., 2020; Bozkurt et al., 2020) in
model-free reinforcement learning. There has been substantial work on
lexicographic objectives in optimisation and RL, including lexicographic
discounted objectives (Skalse et al., 2022; Chatterjee et al., 2006;
Chatterjee, 2007), lexicographic $\omega$-regular objectives (Hahn et al.,
2021), and a combination of safety and discounted objectives (Bozkurt et al.,
2021). However, to the best of our knowledge, this is the first work to
consider the general class of $\omega$-regular objectives with discounted
rewards in model-free RL.

##  2\. Preliminaries

An alphabet $\Sigma$ is a finite set of letters. A finite string (resp.
$\omega$-string) over $\Sigma$ is defined as a finite sequence (resp. an
infinite $\omega$-sequence) of letters from $\Sigma$. We denote the empty
string by $\varepsilon$. We write $\Sigma^{*}$ and $\Sigma^{\omega}$ for the
set of finite and $\omega$-strings over $\Sigma$. A language (resp.
$\omega$-language) $L$ over an alphabet $\Sigma$ is defined as a set of finite
strings (resp. $\omega$-strings).

###  2.1. Markov Decision Processes

Let $\mathcal{D}(S)$ denote the set of all discrete distributions over $S$.

###### Definition 0 (Markov decision process).

A Markov decision process (MDP) $\mathcal{M}$ is a tuple $(S,s_{0},A,T,AP,L)$,
where

  * •

$S$ is a finite set of states and $s_{0}\in S$ is the initial state,

  * •

$A$ is a finite set of actions,

  * •

$T\colon S\times A\to\mathcal{D}(S)$ is the probabilistic transition function,

  * •

$AP$ is the set of atomic propositions (observations), and

  * •

$L\colon S\to 2^{AP}$ is the labelling function.

For any state $s\in S$, we let $A(s)$ denote the set of actions that can be
selected in state $s$. A sub-MDP of $\mathcal{M}$ is an MDP
$\mathcal{M}^{\prime}=(S^{\prime},A^{\prime},T^{\prime},AP,L^{\prime})$, where
$S^{\prime}\subset S$, $A^{\prime}\subseteq A$ is such that
$A^{\prime}(s)\subseteq A(s)$ for every $s\in S^{\prime}$, and $T^{\prime}$
and $L^{\prime}$ are analogous to $T$ and $L$ when restricted to $S^{\prime}$
and $A^{\prime}$. Moreover $\mathcal{M}^{\prime}$ is closed under
probabilistic transitions. An MDP is a Markov chain if $A(s)$ is singleton for
all $s\in S$.

For states $s,s^{\prime}\in S$ and $a\in A(s)$, $T(s,a)(s^{\prime})$ equals
$\Pr(s^{\prime}|s,a)$. A run of $\mathcal{M}$ is an $\omega$-word $\langle
s_{0},a_{1},s_{1},\ldots\rangle\in S\times(A\times S)^{\omega}$ such that
$\Pr(s_{i+1}|s_{i},a_{i+1}){>}0$ for all $i\geq 0$. A finite run is a finite
such sequence. For a run $r=\langle s_{0},a_{1},s_{1},\ldots\rangle$ we define
the corresponding labelled run as $L(r)=\langle
L(s_{0}),L(s_{1}),\ldots\rangle\in(2^{AP})^{\omega}$. We write
$\mathit{Runs}^{\mathcal{M}}(\mathit{FRuns}^{\mathcal{M}})$ for the set of
runs (finite runs) of the MDP $\mathcal{M}$ and
$\mathit{Runs}{}^{\mathcal{M}}(s)(\mathit{FRuns}{}^{\mathcal{M}}(s))$ for the
set of runs (finite runs) of the MDP $\mathcal{M}$ starting from the state
$s$. We write $\operatorname{\mathit{last}}(r)$ for the last state of a finite
run $r$.

A strategy in $\mathcal{M}$ is a function
$\sigma\colon\mathit{FRuns}\to\mathcal{D}(A)$ such that
$\operatorname{\mathit{supp}}(\sigma(r))\subseteq
A(\operatorname{\mathit{last}}(r))$, where $\operatorname{\mathit{supp}}(d)$
denotes the support of the distribution $d$. A memory skeleton is a tuple
$M=(M,m_{0},\alpha_{u})$ where $M$ is a finite set of memory states, $m_{0}$
is the initial state, and $\alpha_{u}:M\times\Sigma\to M$ is the memory update
function. We define the extended memory update function
$\hat{\alpha}_{u}:M{\times}\Sigma^{*}\to M$ in a straightforward way. A finite
memory strategy for $\mathcal{M}$ over a memory skeleton $M$ is a Mealy
machine $(M,\alpha_{x})$ where $\alpha_{x}:S{\times}M\to\mathcal{D}(A)$ is the
next action function that suggests the next action based on the MDP and memory
state. The semantics of a finite memory strategy $(M,\alpha_{x})$ is given as
a strategy $\sigma:\mathit{FRuns}\to\mathcal{D}(A)$ such that for every
$r\in\mathit{FRuns}$ we have that
$\sigma(r)=\alpha_{x}(\operatorname{\mathit{last}}(r),\hat{\alpha}_{u}(m_{0},L(r)))$.

A strategy $\sigma$ is pure if $\sigma(r)$ is a point distribution for all
runs $r\in\mathit{FRuns}^{\mathcal{M}}$ and is mixed (short for strictly
mixed) if
$\operatorname{\mathit{supp}}(\sigma(r))=A(\operatorname{\mathit{last}}(r))$
for all runs $r\in\mathit{FRuns}^{\mathcal{M}}$. Let
$\mathit{Runs}^{\mathcal{M}}_{\sigma}(s)$ denote the subset of runs
$\mathit{Runs}^{\mathcal{M}}(s)$ that correspond to strategy $\sigma$ with
initial state $s$. Let $\Sigma_{\mathcal{M}}$ be the set of all strategies. We
say that $\sigma$ is stationary if
$\operatorname{\mathit{last}}(r)=\operatorname{\mathit{last}}(r^{\prime})$
implies $\sigma(r)=\sigma(r^{\prime})$ for all finite runs
$r,r^{\prime}\in\mathit{FRuns}^{\mathcal{M}}$. A stationary strategy can be
given as a function $\sigma:S\to\mathcal{D}(A)$. A strategy is positional if
it is both pure and stationary.

An MDP $\mathcal{M}$ under a strategy $\sigma$ results in a Markov chain
$\mathcal{M}_{\sigma}$. If $\sigma$ is a finite memory strategy, then
$\mathcal{M}_{\sigma}$ is a finite-state Markov chain. The behaviour of an MDP
$\mathcal{M}$ under a strategy $\sigma$ and starting state $s\in S$ is defined
on a probability space
$(\mathit{Runs}^{\mathcal{M}}_{\sigma}(s),\mathcal{F}_{\mathit{Runs}^{\mathcal{M}}_{\sigma}(s)},{\Pr}^{\mathcal{M}}_{\sigma}(s))$
over the set of infinite runs of $\sigma$ with starting state $s$. Given a
random variable $f\colon\mathit{Runs}^{\mathcal{M}}\to\mathbb{R}$, we denote
by $\mathbb{E}^{\mathcal{M}}_{\sigma}(s)\left\\{f\right\\}$ the expectation of
$f$ over the runs of $\mathcal{M}$ originating at $s$ that follow the strategy
$\sigma$.

###  2.2. Discounted Reward Objectives

The learning objective over MDPs in RL is often typically expressed using a
Markovian reward function, i.e. a function $\rho\colon S\times A\times
S\to\mathbb{R}$ assigning utility to transitions. A rewardful MDP is a tuple
$\mathcal{M}=(S,s_{0},A,T,\rho)$ where $S,s_{0},A,$ and $T$ are defined in a
similar way as for MDP, and $\rho$ is a Markovian reward function. A rewardful
MDP $\mathcal{M}$ under a strategy $\sigma$ determines a sequence of random
rewards ${\rho(X_{i-1},Y_{i},X_{i})}_{i\geq 1}$, where $X_{i}$ and $Y_{i}$ are
the random variables denoting the $i$-th state and action, respectively. For
$\lambda\in[0,1[$, the discounted reward
$\mathsf{Disct}(\lambda)^{\mathcal{M}}_{\sigma}(s)$ is defined as
$\lim_{N\to\infty}\mathbb{E}^{\mathcal{M}}_{\sigma}(s)\Big{\\{}\sum_{1\leq
i\leq N}\lambda^{i-1}\rho(X_{i-1},Y_{i},X_{i})\Big{\\}}$. We define the
optimal discounted reward $\mathsf{Disct}^{\mathcal{M}}_{*}(s)$ for a state
$s\in S$ as
$\mathsf{Disct}^{\mathcal{M}}_{*}(s)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\sup_{\sigma\in\Sigma_{\mathcal{M}}}\mathsf{Disct}^{\mathcal{M}}_{\sigma}(s)$.
A strategy $\sigma$ is discount-optimal if
$\mathsf{Disct}^{\mathcal{M}}_{\sigma}(s)=\mathsf{Disct}^{\mathcal{M}}_{*}(s)$
for all $s{\in}S$.

Often, complex learning objectives cannot be expressed using Markovian reward
signals. A recent trend is to express learning objectives using finite-state
reward machines (Icarte et al., 2022). A (nondeterministic) reward machine is
a tuple $\mathcal{R}=(\Sigma,U,u_{0},\delta,\rho)$ where $U$ is a finite set
of states, $u_{0}{\in}U$ is the starting state, $\delta\colon
U{\times}\Sigma\to 2^{U}$ is the transition relation, and $\rho\colon
U\times\Sigma\times U\to\mathbb{R}$ is the reward function.

Given an MDP $\mathcal{M}=(S,s_{0},A,T,AP,L)$ and a reward machine
$\mathcal{R}=(2^{AP},U,u_{0},\delta,\rho)$, their product
$\mathcal{M}{\times}\mathcal{R}=(S{\times}U,(s_{0},u_{0}),(A{\times}U),T^{\times},\rho^{\times})$
is a rewardful MDP where
$T^{\times}\colon(S{\times}U)\times(A{\times}U)\to\mathcal{D}(S{\times}U)$ is
such that

$((s,u),(a,u^{\prime}))(({s}^{\prime},{u}^{\prime}))\mapsto\begin{cases}T(s,a)({s}^{\prime})&\text{if
}u^{\prime}{\in}\delta(u,L(s))\\\ 0&\text{otherwise.}\end{cases}$

and
$\rho^{\times}\colon(S{\times}U)\times(A{\times}U)\times(S{\times}U)\to\mathbb{R}$
is defined such that
$\rho^{\times}((s,u),(a,u^{\prime}),(s^{\prime},u^{\prime}))$ equals
$\rho(u,L(s),u^{\prime})$ if $(u,L(s),{u}^{\prime})\in\delta$. For discounted
reward objective, the optimal strategy of $\mathcal{M}{\times}\mathcal{R}$ are
positional on $\mathcal{M}{\times}\mathcal{R}$. Moreover, these positional
strategies characterise a finite memory strategy (with memory skeleton based
on the states of $\mathcal{R}$ and the next-action function based on the
positional strategy) over $\mathcal{M}$ maximising the learning objective
given by $\mathcal{R}$.

In our reductions, we make use of total reward objective
$\mathsf{ETotal}^{\mathcal{M}}_{*}(s)$ defined in a similar fashion as the
discounted objective when the discount factor $\lambda$ is equal to $1$. The
concepts of expected total reward and optimal strategy is defined in an
analogous manner.

###  2.3. Omega-Regular Specifications

###### Definition 0 (Büchi automaton).

A _Büchi automaton_ is a tuple ${\mathcal{A}}=(\Sigma,Q,q_{0},\delta,F)$,
where

  * •

$\Sigma$ is a finite _alphabet_ ,

  * •

$Q$ is a finite set of _states_ ,

  * •

$q_{0}\in Q$ is the _initial state_ ,

  * •

$\delta\colon Q\times\Sigma\to 2^{Q}$ is the _transition function_ , and

  * •

$F\subseteq Q\times\Sigma\times Q$ is the set of _accepting transitions_.

A _run_ $r$ of ${\mathcal{A}}$ on $w\in\Sigma^{\omega}$ is an $\omega$-word
$r_{0},w_{0},r_{1},w_{1},\ldots$ in $(Q\times\Sigma)^{\omega}$ such that
$r_{0}{=}q_{0}$ and, for $i>0$, $r_{i}\in\delta(r_{i-1},w_{i-1})$. Each triple
$(r_{i-1},w_{i-1},r_{i})$ is a _transition_ of ${\mathcal{A}}$. We write
$\operatorname{\mathsf{inf}}(r)$ for the set of transitions that appear
infinitely often in the run $r$. A run $r$ of ${\mathcal{A}}$ is _accepting_
if $\operatorname{\mathsf{inf}}(r)\cap F\neq\emptyset$. The _language_
$\mathcal{L}(\mathcal{A})$ of ${\mathcal{A}}$ is the subset of words in
$\Sigma^{\omega}$ that have accepting runs in ${\mathcal{A}}$. A language is
$\omega$-_regular_ if it is accepted by a Büchi automaton.

Given an MDP $\mathcal{M}=(S,s_{0},A,T,AP,L)$ and a Büchi automaton
$\mathcal{A}=(2^{AP},Q,q_{0},\delta,F)$, their _product_
$\mathcal{M}\times\mathcal{A}=(S{\times}Q,(s_{0},q_{0}),A{\times}Q,T^{\times},F^{\times})$
is an MDP with accepting transitions $F^{\times}$ where
$T^{\times}\colon(S{\times}Q)\times(A{\times}Q)\to\mathcal{D}(S\times Q)$ is
such that

$((s,q),(a,q^{\prime}))(({s}^{\prime},{q}^{\prime}))\mapsto\begin{cases}T(s,a)({s}^{\prime})&\text{if
}(q,L(s,a,{s}^{\prime}),{q}^{\prime}){\in}\delta\\\
0&\text{otherwise.}\end{cases}$

The set of accepting transitions $F^{\times}\subseteq(S\times Q)\times(A\times
Q)\times(S\times Q)$ is defined by
$((s,q),(a,q^{\prime}),(s^{\prime},q^{\prime}))\in F^{\times}$ if, and only
if, $(q,L(s,a,s^{\prime}),q^{\prime})\in F$ and $T(s,a)(s^{\prime})>0$.

A strategy $\sigma$ on the product defines a strategy $\sigma^{\prime}$ on the
MDP with the same value, and vice versa. Note that for a stationary $\sigma$
on the product, the strategy $\sigma$ on the MDP may need memory.

An end-component (De Alfaro, 1998) of an MDP $\mathcal{M}$ is a sub-MDP
$\mathcal{M}^{\prime}$ such that for every state pair $s,s^{\prime}\in
S^{\prime}$ there is a strategy that can reach $s^{\prime}$ from $s$ with
positive probability. A maximal end-component is an end-component that is
maximal under set-inclusion. Every state $s$ of an MDP $\mathcal{M}$ belongs
to at most one maximal end-component. End-components and runs of the product
MDP are defined just like for MDPs. An accepting end-component is an end-
component that contains an accepting transition. A run of
$\mathcal{M}{\times}\mathcal{A}$ is accepting if $\inf(r)\cap
F^{\times}\neq\emptyset$. We define the Büchi satisfaction probability
$\mathsf{BSat}_{\sigma}(s)$ of a strategy $\sigma$ as the probability of this
strategy generating an accepting run, i.e.

$\textrm{Pr}_{\sigma}^{\mathcal{M}\times\mathcal{A}}\big{\\{}r\in\mathit{Runs}_{\sigma}^{\mathcal{M}\times\mathcal{A}}(s,q_{0}):\inf(r)\cap
F^{\times}\neq\emptyset\big{\\}}.$

Similarly, $\mathsf{BSat}(s)$ is the optimal satisfaction probability over the
product, i.e. $\mathsf{BSat}(s)=\sup_{\sigma}\mathsf{BSat}_{\sigma}(s,q_{0})$.
We say that a strategy $\sigma_{*}$ is _Büchi-optimal_ from $s\in S$ if
$\mathsf{BSat}(s)=\mathsf{BSat}_{{\sigma_{*}}}(s,q_{0})$.

##  3\. Omega-Regular Reward Machines

Our definition of $\omega$-regular reward machine integrates the definitions
of reward machines and Büchi automata. The notion of product with an MDP is
defined in a similar fashion. The optimisation objective is to compute optimal
discounted reward over all Büchi-optimal strategies and near-optimal
strategies achieving this reward.

###### Definition 0 ($\omega$-Regular Reward Machine ($\omega$-RM)).

An $\omega$-RM is a tuple $\mathcal{R}=(\Sigma,U,u_{0},\delta,\rho,F)$ where

  * •

$U$ is a finite set of states,

  * •

$u_{0}\in U$ is the starting state,

  * •

$\delta\colon U\times\Sigma\to 2^{U}$ is the transition relation,

  * •

$\rho\colon U\times\Sigma\times U\to\mathbb{R}$ is the reward function, and

  * •

$F\subseteq U\times\Sigma\times U$ is the set of _accepting transitions_.

Given an MDP $\mathcal{M}=(S,s_{0},A,T,AP,L)$ and an automaton
$\mathcal{R}=(2^{AP},U,u_{0},\delta,\rho,F)$, their _product_
$\mathcal{P}=\mathcal{M}\times\mathcal{R}=(S{\times}U,(s_{0},u_{0}),A{\times}U,T^{\times},\rho^{\times},F^{\times})$
is an MDP with initial state $(s_{0},u_{0})$ and accepting transitions
$F^{\times}$ where
$T^{\times}\colon(S{\times}U)\times((A{\times}U))\to\mathcal{D}(S{\times}U)$
is such that:

$T^{\times}((s,u),(a,u^{\prime}))(({s}^{\prime},{u}^{\prime}))=\begin{cases}T(s,a)({s}^{\prime})&\text{if
}u^{\prime}{\in}\delta(u,L(s))\\\ 0&\text{otherwise.}\end{cases}$

The set of accepting transitions $F^{\times}\subseteq(S\times U)\times(A\times
U)\times(S\times U)$ is defined by
$((s,q),(a,q^{\prime}),(s^{\prime},q^{\prime}))\in F^{\times}$ if, and only
if, $(q,L(s),q^{\prime})\in F$ and $T(s,a)(s^{\prime})>0$.

Let us fix the product MDP $\mathcal{P}=\mathcal{M}\times\mathcal{R}$ as the
tuple $(Q,q_{0},A,T,\rho,F)$ for the rest of this section. To define the
optimisation objective for $\omega$-RM, we need to define the following
concepts over the product MDP $\mathcal{P}$.

  * •

The _Büchi satisfaction probability_ $\mathsf{BSat}_{\sigma}(s)$ is the
probability to satisfy the Büchi objective by a strategy $\sigma$ from a given
state $s$ and is defined similar to that for Büchi automata (Section 2.3). The
_optimal satisfaction probability_ $\mathsf{BSat}(s)$ and a Büchi-optimal
strategy $\sigma^{*}$ that achieves these, i.e.,
$\mathsf{BSat}(s_{0})=\mathsf{BSat}_{\sigma^{*}}(s_{0})$ is defined similar to
that for Büchi automata (Section 2.3).

  * •

The _optimal Büchi-discounted value_ $\mathsf{Bval}$ is the optimal discounted
reward among Büchi optimal strategies, i.e.,

$\mathsf{Bval}:q\mapsto\sup_{\sigma}\big{\\{}\mathsf{value}_{\sigma}(q)\mid\mathsf{BSat}(q)=\mathsf{BSat}_{\sigma}(q)\big{\\}}$

where
$\mathsf{value}_{\sigma}:q\mapsto\mathsf{Disct}(\lambda)^{\mathcal{M}}_{\sigma}(q)$
is the discounted value of $\sigma$.

  * •

An _optimal Büchi-discounted strategy_ is a strategy $\sigma$ that attains
optimal Büchi-discounted value, i.e.,
$\mathsf{BSat}(q_{0})=\mathsf{BSat}_{\sigma}(q_{0})$ and, for a given
$\varepsilon>0$ an $\varepsilon$-optimal (near optimal) Büchi-discounted
strategy is such that
$\mathsf{Bval}_{\sigma}(q_{0})>\mathsf{value}_{\sigma}(q_{0})-\varepsilon$.

We seek near-optimal strategies that maximise the chance of satisfying the
Büchi objective, but will only be arbitrarily close to satisfying the
discounted reward objective due to the following observation.

###### Lemma 0.

The optimal Büchi-discounted strategies may not exist.

###### Proof.

Consider an MDP where one can freely choose the next letter from an alphabet
$\\{a,b\\}$ and have a reward of $1$ for $a$ and $0$ for $b$, as well as a
primary Büchi objective to see infinitely many $b$’s, then we cannot achieve
an expected reward of $\frac{1}{1-\lambda}$ while satisfying the Büchi
objective. We can, however, get arbitrarily close, e.g., by producing $a$’s
until a reward $>\frac{1}{1-\lambda}{-}\varepsilon$ is collected for any given
$\varepsilon>0$, and henceforth produce $b$’s. While the optimal Büchi-
discounted value is $\frac{1}{1-\lambda}$, no (finite or infinite memory)
strategy can attain it. ∎

###  3.1. Known MDP: Probabilistic Model Checking

Consider the problem to compute the optimal Büchi-discounted value and near-
optimal strategies when $\mathcal{M}$ and $\mathcal{R}$, and therefore their
product $\mathcal{P}$, are known. A possible first step is to model check the
MDP $\mathcal{P}$ against the Büchi objective. This provides the probability
of achieving the Büchi objective from every state together with a positional
strategy $\sigma^{*}$ of how to achieve it.

Model checking the product MDP $\mathcal{P}=(Q,q_{0},A,T,\rho,F)$ is a
standard operation (Baier and Katoen, 2008; De Alfaro, 1998). One would
typically start with qualitative model checking, which consists of two
intertwined procedures:

  1. (1)

Remove all states in $Q$ from which no accepting transition is reachable with
positive probability. If any states were removed, go to step 2.

  2. (2)

Recursively remove state-action pairs $(q,a)$ where $T(q,a)(q^{\prime}){>}0$
for any state $q^{\prime}$ that has been previously removed, and remove states
$q$ such that all of its state-action pairs $(q,a)$ have already been removed.
If any state was removed at the end of this procedure, go back to step 1.

Both steps work in time linear in the transition graph of $\mathcal{P}$, and a
fixed point is reached in at most $|Q|$ steps, because a new procedure call is
made only if at least one state was removed. The remaining states,
$Q_{1}\subseteq Q$, are those, for which we can satisfy the Büchi objective
almost surely, and the last application of (1) provides such a strategy.

To extend this method to quantitative model checking (computing the optimal
probability of satisfying the Büchi objective), we can simply add, for all
states $q$ removed during the procedure above (whose set will be denoted by
$Q_{<1}=Q\setminus Q_{1}$) and all actions $a$, variables $p_{(q,a)}$ and
$p_{q}$ that represent the probability to win when taking the state-action
pair $(q,a)$ and when starting at $q$, respectively. To calculate the correct
probabilities, we define the following linear program that these probabilities
have to satisfy.  For all $q\in Q_{<1}$ and $a\in A$: $\displaystyle
p_{(q,a)}$ $\displaystyle=\sum_{q^{\prime}\in
Q_{<1}}T(q,a)(q^{\prime})p_{q}+\sum_{q^{\prime}\in Q_{1}}T(q,a)(q^{\prime})$
$\displaystyle p_{q}$ $\displaystyle\geq 0\qquad\text{ and }\qquad p_{q}\geq
p_{(q,a)}$ with the objective to _Minimise_ $\sum_{q\in Q_{<1}}p_{q}$. Note
that we can achieve $p_{q}$ value when starting at $q$ by playing a safe
strategy that at any state, $q^{\prime}$, only uses an action, $a$, such that
$p_{q^{\prime}}=p_{(q^{\prime},a)}$ and such that there is a positive
probability to visit an accepting transition as done in (1).

Compute Near-Optimal Strategies. To find a strategy that is near-optimal with
respect to the discounted reward without sacrificing the probability to
satisfy the Büchi objective we do the following. First, we remove all state-
action pairs $(q,a)$ such that $p_{q}\neq p_{(q,a)}$ from $\mathcal{P}$,
because taking any such action would reduce the probability of generating an
accepting run. Next, we remove all states that have no actions left. Note
that, in the example discussed in Lemma 3.2, we would neither remove any
states nor any state-action pairs. Now, for the remaining states, $q\in
Q^{\prime}$, and state-actions pairs, $(q,a)$, we introduce variables
$\rho_{q}$ and $\rho_{(q,a)}$, respectively. We find the optimal discounted
reward values and a positional strategy $\tau$ that realises them using the
following linear program.  For all $q\in Q^{\prime}$ and $a\in A(q)$:
$\displaystyle\rho_{q}$ $\displaystyle\geq\rho_{(q,a)}$
$\displaystyle\rho_{(q,a)}$ $\displaystyle=\sum_{q^{\prime}\in
Q^{\prime}}T(q,a)(q^{\prime})\big{(}\rho(q,a,q^{\prime})+\lambda\rho_{q^{\prime}}\big{)}\
,$ with the objective to _Minimize_ $\sum_{q\in Q^{\prime}}\rho_{q}$.

In the example shown in Lemma 3.2, this would be to always produce $a$’s—which
would not satisfy the Büchi objective. However, any strategy obtained this way
can either be followed long enough that the value of the tail is marginal, or
we can initially follow this strategy, and switch to a strategy $\sigma^{*}$
that pursues the Büchi objective with a small probability in every step. Both
approaches will lead to a strategy that maximises the probability to satisfy
the Büchi objective (in our example, with probability $1$) while providing an
expected payoff that is near-optimal among the strategies that maximise
satisfying the Büchi objective.

###  3.2. Reinforcement Learning: Reward Translation

When the MDP is not known, we use model-free RL to approximate optimal value
and learn a near optimal strategy. We present a reduction from the product MDP
$\mathcal{P}=(Q,q_{0},A,T,\rho,F)$ to a related MDP $\mathcal{P}_{\lambda}$
such that optimal values from $\mathcal{P}_{\lambda}$ can be used to compute
the optimal value in $\mathcal{P}$.

###### Definition 0 (Reward Translation).

For a product MDP $\mathcal{P}=(Q,q_{0},A,T,\rho,F)$ with discount factor
$\lambda$, consider a related MDP
$\mathcal{P}_{\lambda}=(Q^{\prime},(q_{0},0),A,T^{\prime},\rho,F^{\prime})$,
where:

  * •

$Q^{\prime}=(Q\times\left\\{0,1\right\\})\cup\\{t\\}$ is the state space,
where $t$ is a fresh trap state including the initial state $(q_{0},0)$,

  * •

$T^{\prime}\colon Q^{\prime}\times A\times Q^{\prime}\to[0,1]$ is the
transition function where

$\displaystyle T^{\prime}((q,0),a,(q^{\prime},0))$
$\displaystyle=(1-\lambda)T(q,a,q^{\prime})$ $\displaystyle
T^{\prime}((q,0),a,(q^{\prime},1))$ $\displaystyle=\lambda T(q,a,q^{\prime})$
$\displaystyle T^{\prime}((q,1),a,(q^{\prime},1))$
$\displaystyle=\begin{cases}\zeta T(q,a,q^{\prime})&\text{if
$(q,a,q^{\prime})\in F$}\\\ T(q,a,q^{\prime})&\text{otherwise}\end{cases}$
$\displaystyle T^{\prime}((q,1),a,t)$
$\displaystyle=(1-\zeta)\sum\limits_{\\{q^{\prime}\mid(q,a,q^{\prime})\in
F\\}}T(q,a,q^{\prime})$ $\displaystyle T^{\prime}(t,\sigma,t)$
$\displaystyle=1$

where $\zeta\in(0,1)$ is a parameter,

  * •

and $\rho^{\prime}\colon Q^{\prime}\times A\times Q^{\prime}\to\mathbb{R}$ is
the reward function where

$\displaystyle\rho^{\prime}((q,0),a,(q^{\prime},0))$
$\displaystyle=\rho(q,a,q^{\prime})$
$\displaystyle\rho^{\prime}((q,0),a,(q^{\prime},1))$
$\displaystyle=\rho(q,a,q^{\prime})$
$\displaystyle\rho^{\prime}((q,1),a,(q^{\prime},1))$ $\displaystyle=0$
$\displaystyle\rho^{\prime}((q,1),a,t)$ $\displaystyle=f$
$\displaystyle\rho^{\prime}(t,a,t)$ $\displaystyle=0$

where $f\geq 1$ is a (usually large) parameter.

$q_{0}$$q_{1}$$q_{2}$$1,\rho_{2}$$p,\rho_{0}$$1-p,\rho^{\prime}_{0}$$1,\rho_{1}$m$(q_{0},0)$$(q_{1},0)$$(q_{2},0)$$\lambda,\rho_{2}$$p\lambda,\rho_{0}$$(1-p)\lambda,\rho^{\prime}_{0}$$\lambda,\rho_{1}$$(q_{0},1)$$(q_{1},1)$$(q_{2},1)$$1$$t$$p\zeta$$1-p$$p(1-\zeta)$,
$f$$\zeta$$1-\zeta$,
$f$$(1-p)(1-\lambda),\rho^{\prime}_{0}$$p(1-\lambda),\rho_{0}$$1-\lambda,\rho_{1}$$1-\lambda,\rho_{2}$
Figure 2. A translation of a product MDP with a combined Büchi-discounted
reward objective with a discount factor $\lambda$ on the left hand side to an
MDP with total reward objective on the right hand side. Each transition is
labelled with its probability followed by its reward. Rewards with value $0$
are omitted. Intuitively, the new MDP consists of two phases: the maximisation
of the discounted reward (states labelled $(q_{i},0)$) followed by
maximisation of the Büchi objective (states labelled $(q_{i},1)$). We move
from the first phase to the second with probability $1-\lambda$ in each step.
Any original accepting transition is marked with a green dot and is replaced
in the new MDP with a transition that leads with probability $p(1-\zeta)$ to
the new trap state $t$ and with probability $p\zeta$ to the original target
state, where $p$ is the original transition probability.

An example of this translation is shown in Figure 2. Note that while the MDP
$\mathcal{P}_{\lambda}$ has two additional parameters, $f$ and $\zeta$, it
only has numerical rewards and is therefore simpler to analyse.

The parameter $\zeta$ has a similar meaning as in (Hahn et al., 2019): with
probability $1-\zeta$ one declares that accepting edges will be seen forever
after seeing a single accepting edge. Increasing the value of $\zeta$ means
that the agent needs to see a larger number of accepting edges to obtain the
same probability of declaring that accepting edges will be seen infinitely
often. As in (Hahn et al., 2019), if the Büchi objective is satisfied with
probability $1$ any $0<\zeta<1$ is correct in our reduction. The parameter $f$
is used to weight the value of the Büchi objective relative to the discounted
reward objective. As we will show, for large enough $f$, the two objectives
are ordered lexicographically. For $\mathcal{P}_{\lambda}$, we want to learn
the optimal expected reward. For this, we define

  * •

$\mathsf{value}^{\prime}(r)=\sum_{i=0}^{\infty}\rho^{\prime}(r_{i},a_{i},r_{i+1})$
for any run $r$ and,

  * •

$\mathsf{value}_{\sigma}^{\prime}\colon
q\mapsto\mathbb{E}\big{\\{}\mathsf{value}^{\prime}(r)\mid
r\in\mathit{Runs}^{\sigma}_{q}(\mathcal{P}_{\lambda})\big{\\}}$, and

  * •

$\mathsf{value}^{\prime}\colon
q\mapsto\sup_{\sigma}\mathsf{value}_{\sigma}^{\prime}(q)$, as well as a
strategy $\sigma$ with
$\mathsf{value}_{\sigma}^{\prime}(q_{0})=\mathsf{value}^{\prime}(q_{0})$.

We say that a positional strategy $\sigma$ is $\varepsilon$-consistent with
value function $\mathsf{value}^{\prime}$ on a set $S$ if
$|\mathsf{value}^{\prime}_{\sigma}(q)-\mathsf{value}^{\prime}(q)|<\varepsilon$
for all $q\in S$.

Let us start with an established learning approach for Büchi objectives, which
is a special case for the approach from (Hahn et al., 2019).

###### Theorem 1 (Limit Reachability (Hahn et al., 2019)).

For a product MDP $\mathcal{P}$ and a given parameter $f\geq 1$, there exists
$\varepsilon>0$ and $\zeta^{*}\in(0,1)$ such that, for all
$\zeta\in(\zeta^{*},1)$ and all $q\in Q$,

$\mathsf{value}^{\prime}\big{(}(q,1)\big{)}\in[f\cdot\mathsf{BSat}(q),f\cdot\mathsf{BSat}(q)+\varepsilon],$

and all positional strategies that are $\varepsilon$-consistent with
$\mathsf{value}^{\prime}$ from $Q\times{1}$ are optimal strategies for the
Büchi objective.

###### Theorem 2.

For a given product MDP $\mathcal{P}$ and $\varepsilon\in(0,1)$, there is a
parameter $f^{*}\geq 1$ such that, for all $f\geq f^{*}$, there is a
$\zeta^{*}\in(0,1)$ such that, for all $\zeta\in(\zeta^{*},1)$,

$\mathsf{value}^{\prime}\big{(}(q,0)\big{)}\in[\mathsf{Bval}(q)+f\cdot\mathsf{BSat}(q),\mathsf{Bval}(q)+f\cdot\mathsf{BSat}(q)+\varepsilon].$

###### Proof.

We start with a number of simple observations.

  1. (1)

For every set of parameters, $\mathcal{P}_{\lambda}$ is a total payoff MDP and
therefore has positional optimal strategies.

  2. (2)

For every strategy that provides the optimal probability
$\mathsf{BSat}(q_{0})$ to satisfy the Büchi objective, the following holds:
for all $k\in\mathbb{N}$, under the assumption that the MDP moves to the
$1$-copy after $k$ steps, the expected chance of satisfying the Büchi
objective is $\mathsf{BSat}(q_{0})$. Moreover, this value is
$\leq\mathsf{BSat}(q_{0})$ for every strategy, and, for some
$k^{\prime}\leq|Q|$ and all $k\geq k^{\prime}$, it is $<\mathsf{BSat}(q_{0})$
for a non-optimal positional strategy. Thus, for any positional non-optimal
strategy, there is a probability $p<\mathsf{BSat}(q_{0})$ such that the chance
of meeting the Büchi objective is $\leq p$. Let $p^{*}$ be the maximal such
value. (Note that the set of positional strategies is finite.)

  3. (3)

Let $d$ be the maximal difference in expected discounted payoff between two
strategies. ($d$ can be bounded by maximum value of $\rho$ divided by
$1-\lambda$). Then we choose
$f^{*}\geq\frac{d}{\gamma(\mathsf{BSat}(q_{0})-p^{*})}+1$.

With these observations, we choose $f^{*}$ as in (3) and, for $f\geq f^{*}$,
$\zeta^{*}$ as in Theorem 1. This provides correct strategies for obtaining
the Büchi objective with maximal probability from all positions in the
$1$-copy, and values that approximate $f\cdot\mathsf{BSat}\big{(}(q,1)\big{)}$
with $\varepsilon$ precision.

Let us now consider two positional strategies for $\mathcal{R}_{\gamma}$:
$\sigma$, which maximises the chance of satisfying the Büchi objective, and
$\tau$, which does not. By (3) and Theorem 1, this implies that the expected
reward of $\sigma$ is at least $1-\varepsilon$ better than the expected reward
of $\tau$. Thus, a positional strategy with optimal reward will also maximize
the chance of satisfying the Büchi objective.

Let us now consider two positional strategies for $\mathcal{P}_{\lambda}$ that
are both $\varepsilon$-consistent with $\mathsf{value}$ on $Q\times\\{1\\}$
(and thus optimal w.r.t. the Büchi objective there), $\sigma$ and $\tau$, such
that the expected reward in the $0$-copy of $\sigma$ is at least $\varepsilon$
higher than that of $\tau$. Then, using Theorem 1, the expected reward of
$\sigma$ in $\mathcal{P}_{\lambda}$ is higher than the reward by $\tau$.

Putting these two together, we get that the optimal solution for
$\mathcal{R}_{\gamma}$ provides that, for all $k\in\mathbb{N}$, the
probability of satisfying the Büchi objective after $k$ steps is
$\mathsf{BSat}(q_{0})$ while, among the strategies with this property, the
expected discounted reward is $\varepsilon$-optimal. ∎

Learning. For given parameters, $\mathcal{P}_{\lambda}$ is simply an MDP with
total rewards _and_ contraction on $Q\times\\{0\\}$ and a reachability
objective in $Q\times\\{1\\}\cup\\{t\\}$. The values and strategies to obtain
them can be learned with standard techniques, such as $Q$-learning. Note that
the parameter $\varepsilon$ can be selected after learning is complete since
the strategy for $\mathcal{P}_{\lambda}$ is independent of $\varepsilon$.

###### Theorem 3.

Given $\mathcal{P}_{\lambda}$ and parameters $f$ and $\zeta$, we can use
$Q$-learning to find $\mathsf{value}^{\prime}$ and an optimal strategy
$\sigma$.

These three theorems provide us with a way to robustly infer a near-optimal
strategy for $\mathcal{M}$ from $\mathcal{R}$ for appropriate parameters $f$
and $\zeta$: To obtain a $2\varepsilon$-optimal strategy for $\mathcal{M}$, we
can simply find or approximate an optimal strategy for $\mathcal{R}$. To
transfer this strategy to $\mathcal{M}$, we can follow the $0$-copy
($Q\times\\{0\\}$) long enough; say $k$ steps, so that the contribution of all
but the first $k$ transitions is smaller than $\varepsilon$. We can then move
on to follow the strategy for the $1$-copy ($Q\times\\{1\\}$).

###### Corollary 0.

For a product MDP $\mathcal{P}$, a $\varepsilon>0$ and appropriate parameter
$f\geq 1$ and $\zeta\in(0,1)$, we can infer a near optimal strategy for
$\mathcal{P}$ from a near optimal strategy for $\mathcal{P}_{\lambda}$ with
parameters $f$ and $\zeta$.

##  4\. Experimental Results

---
Name | states | time (s) | $f$ | $\zeta$ | $\gamma$ | $\alpha$ | $\epsilon$ | init | ep-l | ep-n
cheapest | 6 | 0.56 |  |  |  |  | 0.50 |  |  | 3k
promises | 16 | 0.71 |  |  |  |  | 0.50 |  |  | 3k
robot 4x4 | 64 | 0.30 |  |  |  |  | 0.20 |  |  | 1k
virus | 859 | 61.28 |  | 0.95 |  |  |  |  | 50 | 150k
busyRing2 | 169 | 45.38 |  |  |  | 0.005 | 0.75 |  |  | 175k
twoWECs | 6 | 4.80 | 500 |  |  | 0.005 | 0.20 |  |  | 30k
officeZapPatrol | 876 | 165.05 |  | 0.5 |  |  |  | 7 | 100 | 350k
officePreferences | 1248 | 77.27 | 100 | 0 |  | 0.002 |  | 100 | 150 | 200k
officeZapPreferences | 1254 | 111.01 | 100 | 0 |  | 0.005 | 0.01 | 100 | 1500 | 250k
Table 1. Q-learning results. Blank entries indicate that default parameters
are used. The default parameters are $f=10$, $\zeta=0.99$, $\gamma=0.999$,
$\alpha=0.01$, $\epsilon=0.1$, $\text{init}=0$, $\text{ep-l}=20$, and
$\text{ep-n}=20k$. The same external discount factor of $\lambda=0.99$ was
used for all experiments.

We implemented the construction described in Section 3 in the tool Mungojerrie
(Hahn et al., 2023). The construction is implemented on-the-fly, where the
states of the MDP and the $\omega$-regular reward machine are kept independent
and concatenated at each time step. We ran tabular Q-learning on multiple case
studies, as seen in Table 1. Table 1 shows the name of the case study, the
number of states in the product MDP, the time taken for learning in seconds,
the value of $f$, $\zeta$, and algorithm discount factor $\gamma$. The table
also shows the learning rate $\alpha$, the $\epsilon$-greedy exploration rate
$\epsilon$, the value the Q-table was initialised to, the episode reset
length, and the number of training episodes. The episode reset length is the
number of time steps between accepting edges in the second layer that needs to
be exceeded for the episode to be reset. After learning is complete, we verify
that the values of the learned strategy matches the values computed by the
linear programs described in Section 3. This ensures that the learned strategy
can be transformed into an $\varepsilon$-optimal strategy for any
$\varepsilon>0$. For all of our experiments, we use the same external discount
factor $\lambda=0.99$.

Example _cheapest_ shows how quantitative rewards may supplement an
$\omega$-regular specification to steer the agent toward a path of minimum
_cost_ rather than a path of minimum _length_. Example _promises_ illustrates
the use of quantitative rewards to model advances that an agent may get in
return for a promise to fulfil an obligation encoded as an $\omega$-regular
objective. Examples _robot 4x4_ and _virus_ were used in (Hahn et al., 2021)
in the context of multiple $\omega$-regular properties lexicographically
combined. Their use here demonstrates the wider set of specifications allowed
by $\omega$-regular reward machines. In _busyRing2_ , quantitative rewards are
used to measure the fraction of time spent in negotiating the asynchronous
arbitration protocol. In _twoWECs_ , quantitative rewards indicate preference
between sets of states that satisfy the $\omega$-regular specification. The
last three examples are based on the office grid-world discussed in the
introduction. Since these examples require deep exploration in order to
discover the near-optimal strategy, we initialised the Q-table optimistically
to aid exploration.

Overall, our experimental results demonstrate the effectiveness and
versatility of $\omega$-regular reward machines in solving a wide range of RL
problems with complex specifications. By leveraging the power of
$\omega$-regular objectives and discounted rewards, we can specify and learn
complex behaviours and preferences that would be difficult to express with
traditional RL techniques. Moreover, our open-source implementation may allow
researchers and practitioners to easily apply these techniques to their own
problems.

##  5\. Conclusion

Reward machines and formal specifications are two leading reward programming
languages that roughly correspond to imperative (how to give rewards?) and
declarative (what to give rewards for?) ways of expressing programmer’s
intent. This paper presents a hybrid approach that combines the declarative
and imperative specifications. The $\omega$-regular RMs can be constructed by
expressing declarative specification in LTL and the imperative reward
specification as reward machines. The $\omega$-RMs strictly generalise both
reward machines (from finite-horizon behaviour to infinite-horizon) and
$\omega$-regular languages (from qualitative to quantitative satisfaction) in
a natural framework. We presented a parametric reduction from the optimisation
problem over $\omega$-RM to an optimal reward reachability problem that can be
constructed and learned in a model-free manner.

###### Acknowledgements.

This work was supported in part by the EPSRC through grants EP/X017796/1 and
EP/X03688X/1, the NSF through grant CCF-2009022 and the NSF CAREER award
CCF-2146563; and the EU’s Horizon 2020 research and innovation programme
under grant agreements No 864075 (CAESAR).

## References

  * (1)
  * Baier and Katoen (2008) Christel Baier and Joost-Pieter Katoen. 2008.  _Principles of Model Checking_.  MIT Press.
  * Bozkurt et al. (2021) Alper Kamil Bozkurt, Yu Wang, and Miroslav Pajic. 2021\.  Model-Free Learning of Safe yet Effective Controllers. In _2021 60th IEEE Conference on Decision and Control (CDC), Austin, TX, USA, December 14-17, 2021_. IEEE, 6560–6565.  https://doi.org/10.1109/CDC45484.2021.9683634
  * Bozkurt et al. (2020) Alper Kamil Bozkurt, Yu Wang, Michael M. Zavlanos, and Miroslav Pajic. 2020.  Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning. In _International Conference on Robotics and Automation (ICRA)_. 10349–10355.
  * Camacho et al. (2018) Alberto Camacho, Oscar Chen, Scott Sanner, and Sheila A McIlraith. 2018.  Non-Markovian rewards expressed in LTL: Guiding search via reward shaping (extended version). In _GoalsRL, a workshop collocated with ICML/IJCAI/AAMAS_.
  * Camacho et al. (2019) Alberto Camacho, Rodrigo Toro Icarte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A McIlraith. 2019.  LTL and Beyond: Formal Languages for Reward Function Specification in Reinforcement Learning.. In _IJCAI_ , Vol. 19. 6065–6073.
  * Chatterjee (2007) Krishnendu Chatterjee. 2007\.  Markov Decision Processes with Multiple Long-Run Average Objectives. In _FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science_ , V. Arvind and Sanjiva Prasad (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 473–484.
  * Chatterjee et al. (2006) Krishnendu Chatterjee, Rupak Majumdar, and Thomas A Henzinger. 2006.  Markov decision processes with multiple objectives. In _Annual symposium on theoretical aspects of computer science_. Springer, 325–336.
  * Clark and Amodei (2016) Jack Clark and Dario Amodei. 2016.  Faulty Reward Functions in the Wild.  https://openai.com/blog/faulty-reward-functions/.  Accessed on: 01/18/2023.
  * Dave et al. (2022) Vrunda Dave, Shankara Narayanan Krishna, Vishnu Murali, and Ashutosh Trivedi. 2022\.  Optimal Repair for Omega-Regular Properties. In _Automated Technology for Verification and Analysis, ATVA 2022_ _(Lecture Notes in Computer Science, Vol. 13505)_ , Ahmed Bouajjani, Lukás Holík, and Zhilin Wu (Eds.). Springer, 354–370.
  * De Alfaro (1998) Luca De Alfaro. 1998\.  _Formal verification of probabilistic systems_.  Ph.D. Dissertation. Stanford University.
  * Gaon and Brafman (2020) Maor Gaon and Ronen Brafman. 2020.  Reinforcement Learning with Non-Markovian Rewards. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34-04. 3980–3987.
  * Hahn et al. (2019) Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. 2019.  Omega-Regular Objectives in Model-Free Reinforcement Learning. In _Tools and Algorithms for the Construction and Analysis of Systems_. 395–412.  LNCS 11427.
  * Hahn et al. (2020a) Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. 2020a.  Faithful and Effective Reward Schemes for Model-Free Reinforcement Learning of Omega-Regular Objectives. In _ATVA: Automated Technology for Verification and Analysis_. 108–124.  LNCS 12302.
  * Hahn et al. (2020b) Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. 2020b.  Model-Free Reinforcement Learning for Stochastic Parity Games. In _CONCUR: International Conference on Concurrency Theory_. 21:1–21:16.  LIPIcs 171.
  * Hahn et al. (2021) Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. 2021.  Model-Free Reinforcement Learning for Lexicographic Omega-Regular Objectives. In _Formal Methods, FM 2021_. 142–159.  LNCS 13047.
  * Hahn et al. (2023) Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. 2023.  Mungojerrie: Linear-Time Objectives in Model-Free Reinforcement Learning. In _Tools and Algorithms for the Construction and Analysis of Systems_. 527–545.  LNCS 13993.
  * Hasanbeig et al. (2019) Mohammadhosein Hasanbeig, Yiannis Kantaros, Alessandro Abate, Daniel Kroening, George J Pappas, and Insup Lee. 2019.  Reinforcement learning for temporal logic control synthesis with probabilistic satisfaction guarantees. In _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 5338–5343.
  * Icarte et al. (2018) Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila McIlraith. 2018.  Using reward machines for high-level task specification and decomposition in reinforcement learning. In _International Conference on Machine Learning_. 2107–2116.
  * Icarte et al. (2022) Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A McIlraith. 2022.  Reward machines: Exploiting reward function structure in reinforcement learning.  _Journal of Artificial Intelligence Research_ 73 (2022), 173–208.
  * Oura et al. (2020) Ryohei Oura, Ami Sakakibara, and Toshimitsu Ushio. 2020\.  Reinforcement Learning of Control Policy for Linear Temporal Logic Specifications Using Limit-Deterministic Generalized Büchi Automata.  _IEEE Control. Syst. Lett._ 4, 3 (2020), 761–766.  https://doi.org/10.1109/LCSYS.2020.2980552
  * Sadigh et al. (2014) Dorsa Sadigh, Eric S Kim, Samuel Coogan, S Shankar Sastry, and Sanjit A Seshia. 2014.  A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications. In _Conference on Decision and Control (CDC)_. 1091–1096.
  * Skalse et al. (2022) Joar Skalse, Lewis Hammond, Charlie Griffin, and Alessandro Abate. 2022.  Lexicographic multi-objective reinforcement learning.  _arXiv preprint arXiv:2212.13769_ (2022).
  * Sutton and Barto (2018) Richard S. Sutton and Andrew G. Barto. 2018.  _Reinforcement Learning: An Introduction_ (second ed.).  MIT Press.


††thanks: English translation of the original title Über quantentheoretische
Umdeutung kinematischer und mechanischer Beziehungen taken from B. L. Waerden,
ed., Sources of Quantum Mechanics, Dover Publications, Inc., New York, 1968

# Translation of Werner Heisenberg’s Paper ”Quantum-Theoretical
Reinterpretation of Kinematic and Mechanical Relations” Zeitschrift für Physik
33, 1925, 879-893 into Czech language

Tomáš Mančal  Faculty of Mathematics and Physics, Charles University, Ke
Karlovu 5, CZ-121 16 Prague, Czech Republic

###### Abstract

To facilitate teaching of quantum mechanics on undergraduate and even advanced
secondary school levels, we present an unabridged translation of the original
German text of the famous Werner Heisenberg’s breakthrough paper of 1925 into
Czech language. While the paper introduces fundamentally new concepts into
mechanics, and it contains a relatively large number of equations, its
conceptual side is surprisingly lightweight when it comes to the use of
advanced mathematics. The discussions contained in its Section 1 allow
students of quantum mechanics to contemplate the reasons for the inadequacy of
classical kinematic concepts in the micro-world. Understanding of the
kinematic transition from real valued functions to complex valued ”matrices”,
which is the central point of the paper, can be reached with relatively
elementary mathematics. Translations of the Heisenberg’s work into languages
other than English provide a unique opportunity to introduce the great
scientific concepts of quantum mechanics first hand to a broader audience of
students who have yet to reach proficiency in the current scientific lingua
franca. The present translation is equipped with footnotes explaining the
notation, identifying several typos and pointing out sudden changes in
notation in the original paper.

##  I Introduction

In his famous paper Heisenberg (1925), Über quantentheoretische Umdeutung
kinematischer und mechanischer Beziehungen, often referred to only as
Umdeutung, Werner Heisenberg formulated the first version of modern quantum
mechanics. This formulation later merged with the equivalent, but formally
different formulation of Erwin Schrödinger, developed around the same time.
Historically, the paper was quickly superseded by a mathematically much more
concise matrix mechanics of Born and Jordan (and eventually Heisenberg
himself) Born and Jordan (1925); Born et al. (1926), and it might therefore
seem of a historical value only. Quantum mechanics as we know and teach it
today is barely recognizable in the Umdeutung paper, and Heisenberg’s train of
thoughts was deemed incomprehensible even by some of the most accomplished
theoretical physicists of our days Weinberg (1992). Nevertheless, close
examination of the paper in the context of works which preceded it Blum et al.
(2017), and successful attempts to reconstruct Heisenberg’s calculations
(whose details are largely missing in the paper itself) Aitchison et al.
(2004), seem to reveal a rich source of material for introductory discussion
of quantum mechanics Di Mauro and Naddeo (2021).

In his introductory paragraphs, Heisenberg provides some justification for his
dismissal of classical kinematics in the quantum realm. As he reveals already
in his brief abstract, he strives to construct a theory based on observable
quantities only. Such a motivation is very likely insufficient to rigorously
justify Heisenberg’s steps, as noted by philosophers and historians of
science, see Beller (1999); Wüthrich (2016), and as confirmed by the fact that
the later successful quantum theory operates with another hardly observable
quantity, the state vector. Heisenberg’s motivation was even criticised by
Einstein as being ”quite wrong” approach to theoretical science ”on principle”
(see Heisenberg (1971), p. 63, or quoted in Wüthrich (2016) in a different
translation). Students would therefore not be well served, if Heisenberg’s
introductory paragraphs were presented to them as representative of some
rigorous scientific methodology. Nevertheless, the technical side of
Heisenberg’s discussion undoubtedly sets the stage for his crucial
proposition, namely, to replace classical kinematics based on the real
functions, with a new kinematic concept of an ensemble of complex quantities
(later recognized as matrices by Born Born and Jordan (1925)). Heisenberg, in
his introductory paragraphs, points out the failure of the electron orbit
concept in the theoretical attempts of the so-called Old Quantum Theory (OQT)
to understand multi-electron atoms. As he thinks in terms of observable
quantities, Heisenberg always stays close to the theory of light-matter
interaction. He sees the failures of the OQT, which is essentially just
classical physics augmented by some additional rules and constrains, as a
failure of the classical kinematics - classical description of light
absorption and emission is at odds with empirical laws deduced from
observations of atomic phenomena. Heisenberg’s brief discussion of the
elementary classical theory of radiation serves one important goal, namely, to
show how the electron motion, represented by a time-dependent function of
position and its time derivatives, enters the expressions for the radiated
fields. As the classical quantities enter the expression for fields in various
powers, the central questions concerning the new kinematics is posed by
Heisenberg the following way: If instead of a classical quantity $x(t)$ we
have a quantum-theoretical quantity, what quantum-theoretical quantity will
appear [in the theory of radiation] in place of $x^{2}(t)$ van der Waerden
(1968).

To answer this question, Heisenberg compares the main properties of radiation
frequencies as predicted by the classical theory with those expected from the
(future) quantum theory. He identifies a new rule of combination
(multiplication) of oscillatory components of the electron’s periodic motion,
which ensures that only those frequencies, which satisfy the (quantum) Ritz
combination principle, ever appear in the quantum theory of radiation (in an
arbitrary order of perturbation theory). His new rules allow him to
demonstrate validity of the new kinematics by solving several one-dimensional
problems, such as the harmonic and anharmonic oscillators.

While the application part of the paper is very technical, its conceptual
part, in which the new kinematics is motivated and constructed, can be turned
into an accessible narrative motivating the highly non-trivial step of
introducing operators to the mechanical theory of atomic phenomena. All this
with secondary school mathematics only.

The present paper provides an unabridged translation of the Umdeutung paper
into Czech language, and it suggests a narrative through which sections of the
paper can be used to explain fundamental concepts of quantum mechanics to
undergraduate and advanced secondary school students, as well as to interested
lay public. In Section II we propose the outline of such an exposition of
quantum mechanics to the students. Section III is concerned with a brief
description of the translation, and with the discussion of the footnote
explaining difficult or ambiguous places of Heisenberg’s paper. The
translation itself is present in the Appendix.

##  II Possible usage of the Umdeutung paper in education

Original scientific papers provide a unique perspective on the development and
practices of science. This perspective is useful to both students and
interested lay readership Lightman (2006). In the age of open access
publication, the latest advances in science become accessible to interested
readers, provided that they are proficient in English. Historical development
of quantum theory is one of the last major scientific revolutions, which are
originally recorded mainly in a language other than English. However, the
importance of the first hand access to the founding papers of quantum
mechanics for the present and future generation of historians and educators is
such that the most important original works were translated into English
relatively early on van der Waerden (1968).

Using Heisenberg’s Umdeutung paper in physics education is certainly not a new
idea Di Mauro and Naddeo (2021). In this section, we will describe a possible
narrative motivating, on the basis of the Umdeutung paper, the necessity to
replace the real valued functions of classical mechanics with some new
mathematical objects more suitable for the description of atomic phenomena.
The narrative describes tentative thoughts of a theoretical physicist, who,
facing unsolved problems in atomic physics, searches for new mathematics
satisfying the known properties of atomic systems. Although we refer to Werner
Heisenberg in the sections below, we do not assume anything about his actual
historical thoughts and motivations. We only create a plausible narrative
based on his text to allow students, with the assistance of the teachers, to
rediscover the quantum ”multiplication” rules for themselves.

### Classical Periodic Motion.

Before they venture into the quantum physics, the students need to get
acquainted with the properties of the classical periodic motion. Just as in
Heisenberg’s paper, the discussion can be conveniently limited to the motion
of a particle in a one dimensional potential only. Starting with a particle at
rest at a certain displacement from the bottom of the potential, it is
possible to visually demonstrate to the students (using graphs or computer
animation) that the particle’s motion can be constructed by adding together
cosines of some basic frequency $\omega$, and its integer multiples (the
higher harmonics). The frequency is obtained directly from the period $T$ of
the classical motion as $\omega=\frac{2\pi}{T}.$ The position $x(t)$ of the
particle as a function of time can be then written down as

$x(t)=\sum_{n=0}^{\infty}b_{n}\cos(n\omega
t)=\sum_{n=-\infty}^{\infty}a_{n}e^{in\omega t},$ (1)

where $a_{n}=b_{n}/2$ for $n>0$ and $a_{n}=b_{-n}/2$ for $n<0$. All this can
be explained without any specific reference to Fourier series. At this point
it needs to be discussed with the students that classical theory predicts that
electromagnetic waves originating from the particle’s periodic motions will
contain components with frequencies $n\omega$, for $n=1,2,\dots$. This is a
fact well known to Heisenberg, and it is implicitely used in his introductory
sections.

### Frequencies of the classical and quantum periodic motion.

The second step in the exposition of Heisenberg’s ideas is the discussion of
Bohr’s version of the Ritz combination principle. This principle states that
the frequencies of light emitted from quantum systems, such as atoms,
correspond to differences in energy between stationary states of the systems:

$\omega_{nm}=\frac{\varepsilon_{n}-\varepsilon_{n}}{\hbar}.$ (2)

Here, one should point out and discuss the crucial difference in behaviour of
the classical and quantum frequencies. The classical frequencies are all
integer multiples of a certain fundamental frequency $\omega$. As a
consequence, addition of any two allowed frequencies leads to an allowed
frequency:

$n\omega+m\omega=(n+m)\omega.$ (3)

On the contrary, the quantum frequencies as differences between pairs from a
given set of real numbers (system’s energies) cannot be arbitrarily combined
to return an allowed quantum frequency. Adding two frequencies

$\omega_{nm}+\omega_{kl}=\frac{\epsilon_{n}-\epsilon_{m}+\epsilon_{k}-\epsilon_{l}}{\hbar},$
(4)

does not yield an allowed frequency in the form of Eq. (2) unless two of the
four energies cancel. This is only possible if $m=k$ or and $n=l$ (with the
exception of accidental degeneracy in the spectrum). Why is this important
will become clear in the next step of the exposition.

### Classical kinematics

Classical coordinate $x(t)$ of the periodic motion and its time derivatives
enter the expressions for the radiation in various powers (see Heisenberg
(1925), Section 1). Heisenberg’s kinematic questions is: how to calculate the
oscillatory components of quantities such as $x(t)$ and $y(t)$, when the
corresponding coefficients in Eq. (1) for $x(t)$ and $y(t)$ are known?
Classical rule for combining the coefficients is straightforwardly obtained
from ordinary rules of multiplication. The multiplication of $x(t)y(t)$
amounts to multiplication of two polynomials, in which all terms of $x(t)$
multiply all terms of $y(t)$, e.g.

$a_{n}e^{in\omega t}b_{m}e^{im\omega t}=a_{n}b_{m}e^{i(n+m)\omega t}.$ (5)

If we are to calculate a coefficient of the frequency $k\omega$, where $k$ is
an integer, in the expansion of $x(t)y(t)$, we collect all coefficients, Eq.
(5), such that $n+m=k$. This gives

$c_{k}=\sum_{n}a_{n}b_{k-n}.$ (6)

Here, we removed the coefficient $e^{ik\omega t}$ from the both sides of Eq.
(6). Because $(n+m)\omega$ is always a valid frequency of the motion, there is
no conflict between the classical rules of frequency composition, Eq. (3), and
the classical description of motion by real valued functions.

### Quantum kinematics

As far as we can deduce from Heisenberg’s paper, in the search for a new
quantum kinematics, his main idea is to make sure that the quantum frequency
composition rules, Eq. (4), is automatically satisfied in all operations with
quantum quantities. This is in line with the function that kinematics usually
has in physics. The notion of electrons orbit (or position, path) $x(t)$ has
failed to deliver meaningful results in the OQT. Heisenberg therefore frees
himself from $x(t)$, Eq. (1), as a sum of oscillatory coefficients, and
concentrates on the oscillatory components themselves. They, as an ensemble of
quantities, should now carry the physics of the periodic motion. Quantum
description of periodic motion is thus based on oscillatory terms

$a_{nm}e^{i\omega_{nm}t},$ (7)

where the coefficients $a_{nm}$ now carry two indices, to reflect the double-
index nature of the quantum frequencies. Just as the classical coefficients
$a_{n}$ enter the expression for the oscillatory component of the classical
radiation field (through expressions for $\dot{x}(t)$, $\ddot{x}(t)$ and so
on), Heisenberg expects that terms such as those in Eq. (7) will enter
corresponding quantum expressions for the radiation field.

Let us now represent the quantity $x(t)$ by coefficients
$a_{nm}e^{i\omega_{nm}t}$, and the quantity $y(t)$ by coefficients
$b_{nm}e^{i\omega_{nm}t}$. In order for the quantum frequency combination rule
to be satisfied in operations with these coefficients, one cannot let all
members of the ensemble representing $x(t)$ multiply all members of the
ensemble representing $y(t)$ to form representation of $x(t)y(t)$. Only those
coefficient pairs which return valid frequencies can meet in a multiplication,
i.e., only terms such as

$a_{nm}b_{mk}e^{i\omega_{nm}t}e^{i\omega_{mk}t}=a_{nm}b_{mk}e^{i\omega_{nk}t},$
(8)

are allowed. Collecting then all elements resulting in a given frequency
$\omega_{nk}$ we obtain

$c_{nk}=\sum_{m}a_{nm}b_{mk},$ (9)

as the coefficients representing $x(t)y(t)$. In Eq. (9) we removed the phase
factor $e^{i\omega_{nk}t}$ common to both sides. Importantly, in Eq. (9) one
can readily recognize matrix multiplication.

It is now irrelevant whether the coefficients representing the quantum
analogue of a classical quantity are organized into matrices or not. The
coefficients represent possible contributions to the radiation on the given
frequency $\omega_{nk}$, and the rule of their combination, Eq. (9), ensures
that any function of the quantum analog of $x(t)$ continues to deliver only
frequencies allowed by the Ritz combination principle, Eq. (2).

The students can now easily demonstrate on an example of small finite matrices
Di Mauro and Naddeo (2021), that the matrix multiplication is not generally
commutative, i.e. that for the new mathematical objects $\hat{x}(t)$ and
$\hat{y}(t)$, the collections of oscillatory coefficients, we have
$\hat{x}(t)\hat{y}(t)\neq\hat{y}(t)\hat{x}(t)$. Such a behaviour of the newly
constructed quantities, which after all still represent the motion of a
quantum particle, lends further support to the idea that the classical path
and position concepts are inadequate in the atomic realm. In order to fulfill
the requirements for quantum light frequencies, newly constructed quantities
necessarily lose the basic properties of real functions.

Besides the introduction of the concept of matrices (operators), Heisenberg’s
paper also formulates the quantization condition of OQT in a form, which was
later rewritten using the famous commutator of coordinate and momentum
operators. This fact was only recognized later by Born and Jordan Born and
Jordan (1925). Another possibly valuable point of the paper, which gets often
completely overlooked in teaching quantum mechanics, is the use of
correspondence principle, i.e. the discussion of the classical limits of the
quantum mechanics, which certainly played an important role in its invention.
This feature of the Umdeutung paper, as well as the several example
calculations which Heisenberg presents, are beyond the scope of this short
paper, although even here Heisenberg’s paper might be of interest to quantum
mechanics students and educators.

##  III  The Translation into Czech language

To enable an easy access to the complete text of the Umdeutung paper to
advanced undergraduate or secondary school students of the Czech educational
system, who do not speak German or are not yet proficient enough in English
(where a translation is available), we performed a complete translation of its
original German text into Czech language.

The translation follows the original text as faithfully as possible, including
an attempt to keep the structure of sentences (as far as the differences
between the source and target languages allow), and keeping the original
mathematical notation (with a single exception described in the footnotes).
The Czech text is typeset in such a way that the division into pages is kept
as close to the original as possible, and the two texts can be read side by
side. Original footnotes (Arabic numerals) of the paper are kept and also
translated, and a system of new footnotes (lowercase letters) is added to
comment the paper or details of the translation.

The original German text of the Umdeutung paper contains errors in Eqs. (16)
and two equations above Eq. (17). We do not correct the errors in the
translation, but we point them out and explain in the footnotes. In the
application part of the paper, its Section 3, Heisenberg switches from using
$a(n)$ for the coefficients of complex exponentials in the Fourier series,
into denoting the coefficients of cosines by the same expression. This results
in a seemingly missing factor of $4$ in the last equation before Eq. (20) on
page 888 of the German text. The reader is alerted to this sudden switch of
notation in the new footnotes.

The translation was compared to the available English translation from Ref.
van der Waerden (1968). Several more difficult places of the present
translation were harmonized with the English version. The differences in the
meaning between the two translation are minimal.

##  IV Conclusions

Recent progress in quantum technologies, and the media attention these
technologies attract nowadays, bring quantum mechanics to the forefront of
interest of ever younger students. Young people at the undergraduate level or
even advanced secondary school students seeking insight into quantum mechanics
face a likely dilemma of either succumbing to the heavy load of advanced
mathematics, or staying on a surface with only ”second hand” descriptive
accounts of the subject. The possibility to use, first hand, sections of the
original discovery papers to introduce quantum mechanics seems remote at the
first glance. However, with proper set of support materials, and a support
from teachers, Werner Heisenberg’s Umdeutung paper can be used for just this
purpose. Although English occupies an uncontested position of the scientific
lingua franca, with all the benefits which this situation brings, it cannot be
expected in foreseeable future (at least in Europe) that all young students
interested in physics will be sufficiently proficient in English at the time
that they first reach sufficient knowledge of mathematics to understand the
core of Heisenberg’s propositions. Translations into native languages may
serve to overcome the language barrier which otherwise stand between a young
student and her first hand experience of scientific literature. Although some
of the founding papers of quantum mechanics might be written in a somewhat
archaic style, they communicate a unique spirit of discovery, which invites
students to take on the adventures of science.

The present translation represents the first part of a set of teaching
materials to support a first mathematical exposition of quantum mechanics to
undergraduate university students, advanced secondary school students, or
interested members of public.

## References

  * Heisenberg (1925) W. Heisenberg, Zeitschrift für Physik 33, 879 (1925).
  * Born and Jordan (1925) M. Born and P. Jordan, Zeitschrift für Physik 34, 858 (1925).
  * Born et al. (1926) M. Born, W. Heisenberg, and P. Jordan, Zeitschrift für Physik 35, 557 (1926).
  * Weinberg (1992) S. Weinberg, _Dreams of a Final Theory_ (Pantheon, New York, 1992).
  * Blum et al. (2017) A. Blum, M. Jähnert, C. Lehner, and J. Renn, Studies in History and Philosophy of Science Part B - Studies in History and Philosophy of Modern Physics 60, 3 (2017).
  * Aitchison et al. (2004) I. J. R. Aitchison, D. A. MacManus, and T. M. Snyder, American Journal of Physics 72, 1370 (2004).
  * Di Mauro and Naddeo (2021) M. Di Mauro and A. Naddeo, Phys. Sci. Forum 2, 8 (2021).
  * Beller (1999) M. Beller, _Quantum Dialog: the making of a revolution_ (University of Chicago Press, Chicago, 1999).
  * Wüthrich (2016) A. Wüthrich, in _The Philosophy of Historical Case Studies_ , edited by T. Sauer and R. Scholl (Springer, 2016), pp. 285–296.
  * Heisenberg (1971) W. Heisenberg, _Physics and Beyond: Encounters and Conversations_ (Harper and Row, New York, 1971).
  * van der Waerden (1968) B. L. van der Waerden, _Sources of quantum mechanics_ (Dover Publications, New York, 1968).
  * Lightman (2006) A. Lightman, _The Discoveries: Great Breakthroughs in 20th Century Science_ (Vintage Books, New York, 2006).

##  Appendix A Translation of the Umdeutung paper into Czech

See pages ,,1-19 of Heisenberg_preklad.pdf


stable foliation, although it clearly follows from this and part $b)$.

Let $f=f_{1}$ the time-one map. Given $\varphi$ we denote $\tilde{\varphi}$
its average along flow lines
$\tilde{\varphi}(x)=\int_{0}^{1}\varphi(f^{t}x)dt$. Observe that by the above
proposition the family of measures $\mu^{u}=\\{\mu^{u}_{x}\\}_{x\in M}$
satisfy the same conditions as the measures along unstables that we
constructed in section 3.1, therefore all our construction goes through and we
can determine an equilibrium state $\mathrm{m}_{\scriptstyle\tilde{\varphi}}$
for the system $(f,\tilde{\varphi})$ having conditionals along unstables given
by the family $\mu^{u}$. We now relate $\mathrm{m}_{\scriptstyle\varphi}$ and
the equilibrium states for the flow.

Denote by
$\mathscr{Pr}_{\cramped[\scriptstyle]{\Phi}}(M)=\cap_{t\in\mathbb{R}}\mathscr{Pr}_{\cramped[\scriptstyle]{f_{t}}}(M)$
the set of invariant measures for the flow. The topological pressure of the
system $(\Phi,\varphi)$ is given by the variational principle ([WaltersPres],
Corollary $4.12$)

$P_{\scriptstyle\mathit{top}}(\Phi,\varphi)=\sup_{\mathclap{\nu\in\mathscr{Pr}_{\cramped[\scriptstyle]{\Phi}}(M)}}\\{h_{\nu}(\Phi_{1})+\int\varphi
d\nu\\},$ (35)

and the definition of equilibrium state for this system is clear. In what
follows we will write $\mathscr{Eq}(f,\varphi)$ for the set of equilibrium
measures of $(f,\varphi)$, and analogously $\mathscr{Eq}(\Phi,\varphi)$
denotes the set of equilibrium states for $(\Phi,\varphi)$. Clearly
$\mathscr{Eq}(\Phi,\varphi)\subset\mathscr{Eq}(f,\varphi)$, and although in
principle these sets can be different, it is known that

$P_{\scriptstyle\mathit{top}}(\Phi,\varphi)=P_{\scriptstyle\mathit{top}}(f,\varphi).$

On the other hand, using the previous line it is direct to check that
$P_{\scriptstyle\mathit{top}}(\Phi,\varphi)=P_{\scriptstyle\mathit{top}}(f,\tilde{\varphi})$,
therefore it follows

$\mathscr{Eq}(\Phi,\varphi)=\\{\mu\in\mathscr{Pr}_{\cramped[\scriptstyle]{\Phi}}(M):h_{\mu}(f)+\int\tilde{\varphi}d\mu\\}\subset\mathscr{Eq}(f,\tilde{\varphi}).$

######  Proposition 6.3.

If $\Phi$ is a transitive Anosov flow, then the sets
$\mathscr{Eq}(\Phi,\varphi)$ and $\mathscr{Eq}(f,\tilde{\varphi})$ coincide.
Therefore
$\mathscr{Eq}(f,\tilde{\varphi})=\\{\mathrm{m}_{\scriptstyle\tilde{\varphi}}\\}$.

######  Proof 6.4.

Let $A(t,x)=\int_{0}^{t}\varphi(\Phi_{s}x)ds$; then
$A:M\times\mathbb{R}\to\mathbb{R}$ is an additive cocycle over $\Phi$
($A(t+s,x)=A(t,\Phi_{s}x)+A(s,x))$ and $A(1,x)=\tilde{\varphi}$. For
transitive hyperbolic flows it is known (cf. [BowenRuelle])that
$\mathscr{Eq}(\Phi,\varphi)=\\{\mu\\}$, and in particular $\mu$ is ergodic for
the flow (in fact $(\Phi,\mu)$ is a Bernoulli flow). Fix any
$\mathrm{m}\in\mathscr{Eq}(f,\tilde{\varphi})$ and note that since $f$ and
$f^{s}$ commute, $f^{s}\mathrm{m}\in\mathscr{Eq}(f,\tilde{\varphi}\circ
f^{s})$.

Now the cocycle property tells us that

$\displaystyle A(1+s,x)=A(1,f^{s}(x))+A(s,x)=A(s,f(x))+A(1,x)$
$\displaystyle\Rightarrow\tilde{\varphi}\circ
f^{s}(x)-\tilde{\varphi}(x)=A(1,f^{s}(x))-A(1,x)=A(s,f(x))-A(s,x)$

and $\tilde{\varphi}\circ f^{s}$ is cohomologous to $\tilde{\varphi}$, i.e.
its difference is of the form $k(f(x))-k(x)$ for some $k$ (that in this case
is Hölder). It is simple to check that cohomologous potentials have the same
equilibrium states, therefore
$f^{s}\mathrm{m}\in\mathscr{Eq}(f,\tilde{\varphi})$. The measure
$\tilde{\mu}=\int_{0}^{1}f^{s}\mathrm{m}$ is invariant under the flow, and a
equilibrium state for $(f,\tilde{\varphi})$ hence $\tilde{\mu}=\mu$. By
ergodicity of $\mu$ we then deduce that

$f^{s}\mathrm{m}=\mu\quad\forall s\in[0,1]$

and in particular $\mathrm{m}=\mu$.

We can pair this with Theorem B and deduce the following.

######  Theorem 6.5.

Given a transitive Anosov flow $\Phi$ of class $\mathcal{C}^{2}$ that is not a
suspension, there exists a family $\mu^{u}\in\mathrm{Meas}(\mathcal{W}^{u})$
satisfying the following: for any $\mathrm{m}\in\mathscr{Pr}(M)$, if

  1. 1.

$\mathrm{m}$ is $f^{t}$-invariant for some $t\neq\emptyset$, and

  2. 2.

$\mathrm{m}$ has conditionals absolutely continuous with respect to $\mu^{u}$,

then $\mathrm{m}$ is the unique equilibrium state for the system
$(\Phi,\varphi)$.

In a subsequent article [ContributionsErgodictheory] we will use the previous
theorem to investigate properties of the horocyclic flow. In a restricted
setting we will obtain a stronger characterization of equilibrium states.

Here is the last application of these ideas.

######  Corollary 6.6.

Suppose that $\zeta^{cs}\in\mathrm{Meas}(\mathcal{W}^{cs})$ is such that for
every $x\in M$,
$f^{-1}\zeta^{cs}_{fx}=e^{\tilde{\varphi}-P^{\prime}}\zeta^{cs}_{x}$, where
$P^{\prime}\in\mathbb{R}$. Then $\zeta^{cs}=\mu^{cs}$ and
$P^{\prime}=P_{\scriptstyle\mathit{top}}(\varphi)$.

######  Proof 6.7.

The quasi-invariance condition in the hypotheses permit us to compute the
Jacobian of $\zeta^{cs}$ with respect to the unstable holonomy, and this
coincides with the Jacobian of $\mu^{cs}$. We can thus use $\zeta^{cs}$
instead of $\mu^{cs}$ and construct a probability $\mathrm{m}$ that is an
equilibrium state for $(f,\tilde{\varphi})$ (cf. section 3.2), and therefore
it is the unique equilibrium state for $(\Phi,\varphi)$. Using the local
product structure one gets that $\zeta^{cs}=\mu^{cs}$.

###  6.2 Epilogue

We finish our article with some questions and considerations. In this part the
standing hypotheses are the ones of Theorem A.

######  Question 6.8.

Does the existence of the families of measures $\mu^{u},\mu^{s}$ satisfying
the quasi-invariance condition imply the uniqueness of the unique equilibrium
state for $f$?

This question has eluded us for some time, and for the time being the only
cases where uniqueness is established are the ones treated in this article.
Note however that the methods for the two types of potentials are different in
nature, and it seems possible that an unified approach may be available. Maybe
one can start from the following.

######  Question 6.9.

Is always the case that
$\mathrm{m}_{\scriptstyle\varphi}=\tilde{\mathrm{m}}_{\scriptstyle\varphi}$?

Since these measures are ergodic, it would suffice to establish that they are
not singular with respect to each other. Here is example of such situation.

######  Claim 2.

If the center disintegration of the measures $\mu^{cu},\mu^{cs}$ is Lebesgue,
then
$\mathrm{m}_{\scriptstyle\varphi}=\tilde{\mathrm{m}}_{\scriptstyle\varphi}$.

######  Proof 6.10.

It suffices to establish that
$\tilde{\mathrm{m}}_{\scriptstyle\varphi}<<\mathrm{m}_{\scriptstyle\varphi}$.
During the proof we will denote $a\sim b$ to indicate that the quotient
$\frac{a}{b}$ is bounded above and below, with constants independent of
$\epsilon$. Using the proposition 3.24 and the remark after it (the role of
$\epsilon_{2},\epsilon_{1}$ is to guarantee the product structure of the
measure) we get

$\displaystyle\sup_{0<\epsilon<\epsilon_{2}}\frac{\tilde{\mathrm{m}}_{\scriptstyle\varphi}(B(x,\epsilon))}{\mathrm{m}_{\scriptstyle\varphi}(B(x,\epsilon))}\leq
D\cdot\sup_{0<\epsilon<\frac{\epsilon_{1}}{4}}\frac{\mu^{s}_{x}(W^{s}(x,\epsilon))\cdot\mu^{cu}_{x}(P^{cu}(x,\epsilon))}{\mu^{cs}_{x}(P^{cs}(x,\epsilon))\cdot\mu^{u}_{x}(W^{u}(x,\epsilon))}$

where $D$ does not depend on $x$. As $\mu^{cs}_{x}$ has Lebesgue
disintegration,

$\frac{\mu^{s}_{x}(W^{s}(x,\epsilon))}{\mu^{cs}_{x}(P^{cs}(x,\epsilon))}\sim\left(\frac{\epsilon_{0}}{\epsilon}\right)^{c}$

and likewise,

$\frac{\mu^{cu}_{x}(P^{cu}(x,\epsilon))}{\mu^{u}_{x}(W^{u}(x,\epsilon)}\sim\left(\frac{\epsilon}{\epsilon_{0}}\right)^{c}.$

We conclude that there exists some constant $\widetilde{D}>0$ such that for
every $x\in M$ it holds

$\sup_{0<\epsilon<\epsilon_{2}}\frac{\tilde{\mathrm{m}}_{\scriptstyle\varphi}(B(x,\epsilon))}{\mathrm{m}_{\scriptstyle\varphi}(B(x,\epsilon))}\leq\widetilde{D}.$
(36)

This implies that
$\tilde{\mathrm{m}}_{\scriptstyle\varphi}<<\mathrm{m}_{\scriptstyle\varphi}$
and
$\frac{d\tilde{\mathrm{m}}_{\scriptstyle\varphi}}{d\mathrm{m}_{\scriptstyle\varphi}}(x)\leq\widetilde{D}$
for $\mathrm{m}_{\scriptstyle\varphi}\operatorname{-}a.e.(x)$, as consequence
of the standard Lebesgue differentiation theorem for Borel measures. To check
the absolute continuity, assume that $\mathrm{m}_{\scriptstyle\varphi}(A)=0$
and let $r>0$ be arbitrary. Take a sequence of boxes
$\\{B(x_{k},\epsilon_{k})\\}_{k\in\mathbb{N}}$ satisfying

  1. 1.

$A\subset\bigcup_{k\geq 0}B(x_{k},\epsilon_{k})$,

  2. 2.

$\sum_{k=0}^{\infty}\mathrm{m}_{\scriptstyle\varphi}(B(x_{k},\epsilon_{k}))<\frac{r}{\widetilde{D}}$.

Then

$\tilde{\mathrm{m}}_{\scriptstyle\varphi}(A)\leq\sum_{k=0}^{\infty}\tilde{\mathrm{m}}_{\scriptstyle\varphi}(B(x_{k},\epsilon_{k}))\leq\widetilde{D}\sum_{k=0}^{\infty}\mathrm{m}_{\scriptstyle\varphi}(B(x_{k},\epsilon_{k}))<r,$

and since $r>0$ is arbitrary, $\tilde{\mathrm{m}}_{\scriptstyle\varphi}(A)=0$.

The properties of the center disintegration $\mu^{cs}$ and $\mu^{cu}$ along
centrals seem to give important information about the system, although it is
not obvious how to deduce to deduce this information. One possibility is to
use the construction os section 2 as in the following example.

######  Example 6.11.

For $x\in M$ denote by $\lambda_{x}$ the Lebesgue measure on $W^{c}(x)$, and
if $B$ is foliated box corresponding to the center foliation with $x\in B$,
let $\widetilde{\lambda}_{x}^{B}$ be the corresponding probability measure
induced by $\lambda_{x}$ on the plaque of $B$ containing $x$. Assume that
$E^{c}$ is differentiable, and that $\varphi$ is $c$-constant.

######  Claim 3.

For every $x\in M$ the conditionals measures of $\mu^{cu}_{x}$ with respect to
the center foliation are given by $\\{\lambda_{y}\\}_{y\in W^{c}(x)}$.

That is, for $B$ as above with $x\in B$, the conditional measures of
$\mu^{cu}_{x}|B$ with respect to the partition by center plaques of $B$ are
given by $\\{\widetilde{\lambda}_{x}^{B}\\}_{y\in B}$ (in particular the
disintegration is defined everywhere). Similarly for $\mu^{cs}_{x}$.

To see this fix $x\in M,0<\epsilon\leq\epsilon_{1}$ and let
$B=W^{c}(W^{u}(x,\epsilon),\epsilon)$. For $n\geq 0$ let $B_{n}=f^{n}(B)$ and
note that since $f$ is an center isometry then $\forall y\in B_{n}$ the map
$f^{-n}|:W^{c}(y)\cap B_{n}\to W^{c}(f^{-n}y)\cap B$ is an isometry with
respect to the induced metric. As $\mathcal{W}^{c}$ is differentiable, the
disintegration of the Lebesgue measure $\nu|B_{n}=\mathrm{Leb}^{cu}|B_{n}$
along center plaques is given by $\\{\widetilde{\lambda}^{B_{n}}_{y}\\}_{y\in
B_{n}}$, therefore for $\upsilon_{n}=f^{-n}\nu|B_{n}$ its disintegration is
given by $\\{f^{-n}\lambda^{B_{n}}_{y}\\}_{y\in
B_{n}}=\\{\lambda^{B}_{z}\\}_{z\in B}$. This in turn implies that the center
disintegration of $\nu^{n}=e^{S_{n}\varphi}f^{-n}\nu$ is given by

$(\nu^{n})^{c}_{y}=\frac{e^{S_{n}\varphi}}{\int
e^{S_{n}\varphi}d(\upsilon_{n})^{c}_{y}}(\upsilon_{n})^{c}_{y}=(\upsilon_{n})^{c}_{y}=\widetilde{\lambda}_{y}^{c}.$

From this it follows that every section $\nu\in\mathcal{X}$, in particular
$\mu^{cu}$, has the same disintegration, proving our claim.

######  Question 6.12.

What are in general the disintegrations of $\mu^{cs}$ and $\mu^{cu}$ along
center leaves?

We had to impose some restriction in the potentials considered with the sole
purpose of obtaining a family of obtaining a family
$\mu^{u}\in\mathrm{Meas}(\mathcal{W}^{u})$ defined everywhere (and in
particular, depending measurably on the point). As explained in Theorem D,
this is not an artificial restriction of the method, and in fact is a subtle
point. However, the following it is still not clear and more research is
needed.

######  Question 6.13.

What are the conditions and/or obstructions for the existence of a continuous
family $\mu^{u}\in\mathrm{Meas}(\mathcal{W}^{u})$?

In particular:

######  Question 6.14.

Assume the hypotheses of Theorem A and furthermore that $f$ is accessible
(meaning that any pair of points in $M$ can be joined by a finite
concatenation of curves whose derivatives are in $E^{u}\oplus E^{s}$). Does
there exist a continuous family $\mu^{u}\in\mathrm{Meas}(\mathcal{W}^{u})$ in
this case?

We remark that the example given in the Appendix does not satisfy this
condition, but only essential accessibility (any bi-saturated set by
$\mathcal{W}^{s},\mathcal{W}^{u}$ has Lebesgue measure either zero or one).

The fact that equilibrium states are determined by some families of measures
on a dynamical structure (the invariant foliations) seem to indicate strong
restrictions on the geometry of these measures. In particular we can ask the
following.

######  Question 6.15.

Is
$\mathscr{Pr}(M,\mu^{u})=\mathscr{Pr}_{\cramped[\scriptstyle]{f}}(M,\mu^{u})$?

In a shortcoming article [ContributionsErgodictheory] we give an answer to
this for codimension-one Anosov flows.

##  7 Appendix: Proof of Theorem D

Let $A:\mathbb{T}^{2}\to\mathbb{T}^{2}$ be a linear Anosov map with and
consider $f:\mathbb{T}^{2}\times\mathbb{T}^{2}\to\mathbb{T}^{4}$ the group
extension of $A$ given by

$f(x,\theta_{1},\theta_{2})=(A\cdot
x,\theta_{1}+\alpha_{1}k(x),\theta_{2}+\alpha_{2}k(x))$

where $k:\mathbb{T}^{2}\to\mathbb{T}$ is analytic, not cohomologous to
constant, and $(\alpha_{1},\alpha_{1})$ is a Liouville vector (see below).
Then $f$ is a conservative analytic center isometry with center bundle
parallel to the vertical fibers $\\{0\\}\times\mathbb{R}^{2}$. This example
was considered by Dolgopyat [dolgolivsic] in other context. Due to a result of
Katok, Theorem 1 in [Katok1980a], this map is a $K$-automorphism, therefore in
particular its unstable foliation $\mathcal{W}^{u}$ is ergodic.

######  Lemma 7.1.

$\mathcal{W}^{u}$ is minimal.

######  Proof 7.2.

Let $e^{u}$ be a unit vector in $\mathbb{T}^{2}$ generating the unstable
bundle of $A$ and, consider the linear flow
$\psi^{u}_{t}:\mathbb{T}^{2}\to\mathbb{T}^{2}$, $\psi^{u}_{t}(x)=x+t\cdot
e^{u}$. The unstable foliation of $A$ are the orbits of $\psi^{u}$, and it
holds

$A\psi^{u}_{t}(x)=\psi^{u}_{\lambda e^{u}}(Ax)$

where $\lambda>1$ is the unstable eigenvalue of $A$. It is not hard to verify
that the unstable foliation of $f$ is the orbit foliation of the flow
$\hat{\psi}^{u}_{t}:\mathbb{T}^{4}\to\mathbb{T}^{4}$ given by

$\hat{\psi}^{u}_{t}(x,\theta_{1},\theta_{2})=(\psi^{u}_{t}(x),\theta_{1}+\alpha_{1}l_{t}(x),\theta+\alpha_{2}l_{t}(x))$

where
$l_{t}(x)=\sum_{n=1}^{\infty}k(A^{-n}x)-k(A^{-n}\psi^{u}_{t}(x))=\sum_{n=1}^{\infty}k(A^{-n}x)-(k(A^{-n}x)+\frac{t}{\lambda^{n}}e^{u})$;
since $k$ is differentiable the previous series is convergent. In particular
$\hat{\psi}^{u}$ is conservative.

The flow $\psi^{u}$ is uniquely ergodic, $\mathrm{Leb}$ being its invariant
measure, therefore by a classical result due to Furstenberg, either
$\hat{\psi}^{u}_{t}$ is uniquely ergodic (and therefore minimal, since it
preserves $\mu=\mathrm{Leb}\times d\theta_{1}\times d\theta_{2}$), or any
$\hat{\psi}^{u}_{t}$ ergodic invariant measure has atomic disintegration along
the partition given by the vertical tori (i.e., the center foliation of $f$).
See Theorem $4.1$ in [Furstenberg1961]. The later possibility is prohibited by
Katok’s result, as $\hat{\psi}^{u}_{t}$ is ergodic with respect to Lebesgue.

The vector $(\alpha_{1},\alpha_{2})$ is chosen so that
$\frac{\alpha_{1}}{\alpha_{2}}\not\in\mathbb{Q}$, and that for every
$n\in\mathbb{N}$ there exists $m_{n,1},m_{n,2}\in\mathbb{N}$ such that

  * •

$|\alpha_{1}m_{n,1}+\alpha_{2}m_{n,2}|<\frac{1}{m_{n,2}^{n}}$;

  * •

$m_{n,2}\geq m_{n,1}>n$.

Denote $d_{n}(x,\theta_{1},\theta_{2})=\exp(2\pi
i\langle(\theta_{1},\theta_{2}),(m_{n,1},m_{n,2})\rangle)$; then
$d_{n}:\mathbb{T}^{4}\to\mathbb{T}^{2}$ satisfies

$\displaystyle d_{n}(f(x,\theta_{1},\theta_{2}))=\exp(2\pi
i\langle(\theta_{1}+\alpha_{1}k(x),\theta_{2}+\alpha_{2}k(x)),(m_{n,1},m_{n,2})\rangle)$
$\displaystyle=\exp(2\pi
ik(x)\langle(\alpha_{1},\alpha_{2}),(m_{n,1},m_{n,2})\rangle)d_{n}(x,\theta_{1},\theta_{2}).$

Define $\varphi:M\to\mathbb{R}$ by

$\displaystyle\varphi(x,\theta_{1},\theta_{2})$ $\displaystyle=\sum_{n\geq
0}d_{n}(x,\theta_{1},\theta_{2})-d_{n}(f(x,\theta_{1},\theta_{2}))$
$\displaystyle=\sum_{n}\left(1-\exp\Big{(}2\pi
ik(x)\langle(\alpha_{1},\alpha_{2}),(m_{n,1},m_{n,2})\rangle\Big{)}\right)d_{n}(x,\theta_{1},\theta_{2}).$

Observe that $\varphi$ is the $\mathcal{C}^{\infty}$ limit of coboundaries,
therefore $\mathscr{Eq}(f,\varphi)=\mathscr{Eq}(f,0)$. It is clear on the
other hand that the the Lebesgue measure in $\mathbb{T}^{3}$ maximizes entropy

Assume that there exists a family of measures
$\zeta^{u}=\\{\zeta^{u}_{L}:L\in\mathcal{W}^{u}\\}$ satisfying the quasi-
invariance condition $f^{-1}\zeta_{fL}^{u}=e^{\varphi-
h_{\scriptstyle\mathit{top}}}\zeta_{L}$, and depending continuously on the
point. One can choose $k$ so that $\mathcal{W}^{u}$ is minimal, and then by
Theorem B one would have

$\zeta_{L}=e^{\omega_{L}}\mathrm{m}^{u}_{L}$

where $\mathrm{m}^{u}_{L}$ is the corresponding Margulis measure on $L$, and
$\omega_{L}:L\to\mathbb{R}_{>0}$ is continuous. Then we get

$e^{\varphi-
h_{\scriptstyle\mathit{top}}+\omega_{L}}\mathrm{m}^{u}_{L}=f^{-1}(e^{\omega_{fL}\mathrm{m}^{u}_{fL}})=e^{\omega_{fL}\circ
f-h_{\scriptstyle\mathit{top}}}$

and $\varphi=\omega_{fL}\circ f-\omega_{L}$ (since the Margulis measures have
full support). If $k(0)=0$ then $L_{0}=W^{u}(0)$ is fixed, and we get that for
$\omega=\omega_{L_{0}}$,

$\varphi=\omega\circ f-\omega\quad\text{on }L_{0}.$

Observe however that the family $\\{\omega_{W^{u}(x)}\\}_{x}$ depends
continuously on $x$ ($\mu^{u}$ are essentially the Lebesgue measure), and
therefore $\omega$ extends continuously to $M$, thus implying that $\varphi$
is cohomologous to the zero function, with continuous transfer function
$\phi$. However, by taking the Fourier expansion it is direct to check that
necessarily $\phi=\sum_{n}d_{n}$, which is not continuous. This contradiction
shows that our assumption on the existence of $\zeta^{u}$ is incorrect, thus
implying Theorem D.