Counting Reward Automata: Sample Efficient Reinforcement Learning Through The Exploitation of Reward Function Structure

Authors: tristan  bester
benjamin  rosman
steven  james
nangue  tasse
Venue: AAAI_org_2024_Workshop_NuCLeaR
Published: 2023-11-24 14:10:14

Abstract: We present counting reward automata-a finite state machine variant capable of modelling any reward function expressible as a formal language. Unlike previous approaches, which are limited to the expression of tasks as regular languages, our framework allows for tasks described by unrestricted grammars. We prove that an agent equipped with such an abstract machine is able to solve a larger set of tasks than those utilising current approaches. We show that this increase in expressive power does not come at the cost of increased automaton complexity. A selection of learning algorithms are presented which exploit automaton structure to improve sample efficiency. We show that the state machines required in our formulation can be specified from natural language task descriptions using large language models. Empirical results demonstrate that our method outperforms competing approaches in terms of sample efficiency, automaton complexity, and task completion.

Main paper: 
 introduction: 
 In recent years, reinforcement learning (RL) has achieved a number of successes in complex domains ranging from video games (Badia et al. 2020) to robotics (Kumar, Todorov, and Levine 2016; Kalashnikov et al. 2018) . However, these applications have largely been constrained to relatively simple, short-horizon tasks. This is a consequence of the techniques used for learning and reasoning, where approaches have been constrained to strategies relying on endto-end learning systems. This restricts agents from accessing information about the structure of the problem which is known to designers (Marcus 2020) . Consequently, the agent is required to unnecessarily learn information which could have been provided, resulting in poor sample efficiency (Marcus and Davis 2019; Arjona-Medina et al. 2019) Neuro-Symbolic Artificial Intelligence is a subfield of AI that focuses on the integration of neural and symbolic methods with the intention of addressing the inherent weaknesses present in either of the approaches. It has been argued that the rich cognitive models necessary to solve temporally extended tasks require a combination of these approaches (Valiant 2008) . Hierarchical reinforcement learning (HRL) and state machine-based approaches combine symbolic reasoning with machine learning (Mitchener et al. 2022) . These techniques are congruent with the "best of both worlds" perspective at the core of neuro-symbolic learning. Neural systems excel in training while remaining robust to noise in the data. Symbolic systems excel in the representation and manipulation of explicit knowledge (facilitating human-understandable explanations) while supporting provably correct reasoning procedures (Sarker et al. 2021) .While HRL (Barto and Mahadevan 2003) and state machine-based approaches (Icarte et al. 2018 ) have been proposed as potential solutions to learning long-horizon tasks, both methods are hindered by several shortcomings. HRL methods have traditionally been limited by practical challenges including exploration (Kulkarni et al. 2016 ) and reward definition (Eysenbach et al. 2018) . In contrast, state machine-based approaches have shown significant potential in learning optimal policies for temporally extended tasks (Icarte et al. 2022) . Unfortunately, these methods can only express a small set of tasks, limiting their application to a restricted set of problems.We present a solution to long-horizon RL designed to address the limitations of current state-machine-based approaches. In this paper, we define a novel state machine variant known as a Counting Reward Automaton (CRA) capable of modelling any computer algorithm (Hopcroft and Ullman 1995) . Our formulation is strongly reliant on both neural and symbolic methods. We rely on explicit symbol manipulation in the form of graph algorithms and natural language for task specification. We make the following contributions: (i) we propose counting reward automata as a novel abstract machine variant capable of modelling reward functions expressible in any formal language; (ii) we show that the state machines produced by this approach are both intuitive to specify through the use of Large Language Models (LLMs) as well as significantly simpler than those produced by alternative approaches; (iii) we describe how the sample efficiency of any off-policy algorithm can be improved through the use of counterfactual reasoning. A modified version of Q-learning is provided as an illustrative example; (iv) we discuss the conditions under which the proposed algorithms are guaranteed to converge to optimal policies and demonstrate their utility in several complex domains requiring long-horizon plans.A Markov Decision Process (MDP) is a tuple M = ⟨S, A, T, γ, R⟩ where S is the set of states which may be occupied by the agent, A is the set of actions, T : S × A → Π(S) is the transition function which returns a distribution over next states given action a is executed in state s, γ ∈ [0, 1] is a discount factor and R : S ×A → R is a reward function representing the task to be solved. The agent is required to learn a Markov policy π that performs action selection to maximise cumulative reward. The value function encodes the expected return associated with being in a given state. That is the expected total discounted reward when the agent is in a given state s and selecting actions according to some policy π:V π (s) = E π [ ∞ t=0 γ t R(s t , a t , s t+1 )].An alternative value function is the action-value function Q π (s, a), which represents the expected total discounted reward when the agent executes action a in state s and follows policy π thereafter.A Regular Decision Process (Brafman, De Giacomo et al. 2019 ) is a restricted Non-Markovian Decision Process (NMDP). An NDMP is defined identically to an MDP, except that the domains of T and R are finite sequences of states instead of single states: T : S + × A × S → Π(S) and R : S + × A → R. In the RDP formulation, the dependence on history is restricted to regular functions.A reward machine (RM) is a finite state machine that describes the internal structure of the reward function (Icarte et al. 2022 ). An RM operates by mapping abstracted descriptions of the current environment state to reward functions. This allows a single environmental interaction ⟨s, a, s ′ ⟩ to be assigned different reward values based on the active RM state.A reward machine makes use of a set of propositional symbols P which encode high-level events in an environment. The agent is able to detect the events in P. The subset of events taking place in the environment at each time step is used as the input to the machine. The labelling function L : S × A × S → 2 P determines which events are taking place at a given instant in time. That is, the labelling function is used to assign truth values to the propositions in P given an environmental experience. A reward machine defined in an environment with states S and actions A is a tuple R PSA = ⟨U, u 0 , F, δ u , δ r ⟩, where U is a finite set of states, u 0 ∈ U is the initial state, F is a set of terminal states with (U ∩ F = ∅). The state-transition function is defined by the mapping δ u : U × 2 P → U ∪ F . The state-reward function is given by the mapping δ r : U → [S × A × S → R]. A reward machine R PSA begins in the initial state u 0 . At each time step, the machine receives as input the set of high-level events taking place in the environment. Upon receiving this information, the machine transitions between states based on the state-transition function and outputs a reward function as defined by the state-reward function.To address the limited expressive power of reward machines, we introduce a novel abstract machine known as a Counting Reward Automaton (CRA) that is capable of modelling reward functions expressible as recursively enumerable languages. In contrast to RMs, this framework supports tasks described by unrestricted as opposed to regular grammars. Consequently, the formulation is compatible with any NMDP in which the dependence on history is expressible in a formal language. As a result, this framework may be applied to a much larger number of problems than RMs which are only applicable in RDPs.Counter automata may be thought of as finite state automata augmented by a finite number of counter variables. While processing a string, the machine can update the values of its counters based on inputs, and the counters can in turn influence the machine's state transitions. A constraint imposed on the machine is that the value of its counters cannot be decremented below zero.For m ∈ Z, let +m denote the function as defined in lambda calculus λx.x + m. This function is used to modify counter values in response to machine transitions. A kcounter counter machine (Fischer, Meyer, and Rosenberg 1968 ) is defined as a tuple ⟨Q, F, Σ, δ, q 0 ⟩ where Q is a finite set of machine states, F is a finite set of terminal states, Σ is the input alphabet, q 0 is the initial machine state and δ is the state transition function defined asδ : Q × {Σ ∪ {ε}} × {0, 1} k → Q × {+m : m ∈ Z} kwhere k is the number of counter variables and ε is used to denote an empty string. The empty string allows the machine to transition without reading an input symbol.A counter machine processes an input string one symbol at a time. For each input symbol, we use δ to update the machine configuration based on the input symbol and current machine configuration. A machine configuration is defined as ⟨q, c⟩ ∈ Q × N k . Upon reading input symbol σ the machine transitions according to⟨q ′ , c ′ ⟩ = δ(q, σ, Z(c)), where Z : N k → {0, 1} k is a zero-test function defined as Z(c) i := 0 if c i = 0 1 otherwise.A worked example showing how a counter machine operates has been included in the Appendix.We now introduce the CRA framework as an approach to modelling reward in NMDPs. We begin with the definition of a counting reward automaton. This is followed by the introduction of a running example, used to illustrate the operation of a CRA. Finally, we describe how the automaton can be thought of as defining a reward function on an MDP with a larger state space than that of the NDMP.Counting Reward Automaton A CRA is a counter machine that has been augmented with an output function. The output function returns a reward function after each machine transition. A machine transition occurs every time the agent interacts with the environment. An abstract description of this interaction is used as the input to the machine. This causes the machine to transition, producing the reward function used to reward the agent for interaction. Definition 1.1 (Counting Reward Automaton). Given a set of environment states S, a set of actions A and a set of propositional symbols modelling high-level events P, a kcounter counting reward automaton is defined by a tuple ⟨U, F, Σ, ∆, δ, λ, u 0 ⟩, where U is a finite set of non-terminal states, F is a finite set of terminal states(U ∩ F = ∅), Σ = 2 P is the input alphabet, ∆ = [S × A × S → R]is the output alphabet, δ is the state transition functionδ : U ×{Σ∪{ε}}×{0, 1} k → {U ∪F }×{+m : m ∈ Z k }, λ is the output function λ : U × {Σ ∪ {ε}} × {0, 1} k → ∆,and u 0 is the initial machine state. Example Task As a running example, we consider the LetterEnv environment presented in Figure 1 . In this environment, a symbol (letter) is associated with certain positions. Symbols may either be observed infinitely often, or replaced by another symbol after a set number of observations. The agent is able to observe two aspects of the current state, its xy-location as well as the associated symbol (if such a symbol exists). The agent is able to move in any of the four cardinal directions.For this example, the following environmental configuration is used. In each episode, the symbol A may be observed a fixed number of times, before being replaced by the symbol B. The symbols B, C and D may be observed infinitely often. Specifically, the symbol A may be observed N times within an episode, where N is a random variable with a discrete uniform distribution over the set N. The agent is required to observe a sequence of environment symbols which corresponds to a string in the context-free language (CFL) described by the set L = {A N BC N : N ∈ N}. Remark. As the reward model used in this example distinguishes between histories based on properties not expressible as regular expressions over the elements of the set S × A × S (in this case counting how many times a state has been reached) it cannot be expressed as a reward machine.CRA Operation We use three propositions, one to model the presence of each symbol in the agent's current position P = {P A , P B , P C }. After each interaction of the agent with the environment ⟨s, a, s ′ ⟩, the labelling function L is used to compute the input to the machine σ ∈ 2 P . Upon reading the input symbol σ, the machine transitions according to δ and emits a reward function based on λ. This process continues until the machine enters a terminal state.We now describe how a CRA can be used to model the reward function for the example task. For convenience, we make use of a special case of the CRA formulation known as a Constant Counting Reward Automaton (CCRA). After each transition, a CCRA returns a reward value directly as opposed to a reward function which is output by a CRA.Given a set of propositional symbols modelling high-level events P, a constant counting reward automaton is defined as a tuple ⟨U, F, Σ, ∆, δ, λ, u 0 ⟩ where U, F, Σ, δ, λ and u 0 are defined as in a counting reward automaton; however, the output alphabet of the machine is defined as R.Theorem 1. For each constant counting reward automaton, there exists an equivalent counting reward automaton.Proof. See Appendix.A graphical representation of the example CCRA is illustrated in Figure 2 . The machine contains two non-terminal states, one for each subtask in the specification. In the state u 0 , the agent's objective is to observe the symbol A repeatedly. However, in the state u 1 , the agent is required to observe the symbol C repeatedly. Intuitively, the automaton stores the number of A symbols it has seen in its counter. After observing the symbol B, the machine decrements its counter each time the symbol C is observed. Once the counter has been decremented to zero, the machine transitions into a terminal state and emits a reward of one. The automaton is represented as a directed graph. Each vertex in the graph represents a state in the machine, with u 0 being the initial state. Terminal states are represented by filled circles. Associated with each edge in the graph is a tuple ⟨φ, ω, µ, r⟩ in which φ is a propositional logic formula over P, the vector ω contains the zero-tested counter states, µ contains the counter modifiers and r is the reward associated with the transition. A directed edge between the states u i and u j labelled by the tuple ⟨φ, ω, µ, r⟩ means that if the machine is in state u i , the truth assignment L(s, a, s ′ ) = σ satisfies φ, that is σ |= φ, and Z(c) = ω, then the next machine state is equal to u j and the counter values are updated to c + µ. For example, the edge between u 0 and u 1 labelled by ⟨P B , [1], [0], 0⟩ means that the machine will transition from state u 0 to state u 1 without modifying the counter value and emit a reward of one if the machine is in state u 0 with a nonzero counter value when the proposition P B becomes true. The automaton is updated after every agent-environment interaction. For example, if the agent takes action a in state s resulting in the following state s ′ , the machine configuration is updated to ⟨u ′ , c ′ ⟩ = δ(u, L(s, a, s ′ ), Z(c)) and the agent receives a reward of r = λ(u, L(s, a, s ′ ), Z(c))(s, a, s ′ ). Solving the Example Task With a CCRA in place, we proceed to discuss how a solution to the example task can be obtained. As described, the automaton specifies the reward function for the task. The reward is non-Markovian with respect to the ground environment state. That is, the agent's observation of the environment state does not contain sufficient information to determine the reward. For example, consider the case in which the agent observes that it is in the position associated with the symbol B. As this observation does not contain information about the sequence of symbols previously observed, it is insufficient to define the reward. However, the machine configuration can be combined with the ground environment state to produce a Markov state. As in the RM formulation, the automaton can be thought of as defining a reward function on an MDP with an alternate state space. Each state in this MDP is formed by combining an automaton configuration with a ground environment state. We refer to this MDP as the Automaton-Augmented Markov Decision Process (AAMDP). While the general CRA formulation is not limited, we focus on finite-horizon MDPs. That is, we enforce a fixed upper bound on trajectory length. We use the symbol H to denote the maximum length of any trajectory. This value can be used to compute an upper bound on the value of any machine counter. Specifically, H is multiplied by the maximum counter increment defined in δ to produce the upper bound denoted Γ. Definition 1.3 (Automaton-Augmented Markov Decision Process). An automaton-augmented Markov decision process is an MDP in which the reward function is modelled through the use of a counting reward automaton. An AAMDP is a tuple ⟨S, A, T, γ, U, F, Σ, ∆, δ, λ, u 0 ⟩ in which S, A, T and γ are defined based on an environment representation, and U, F, Σ, ∆, δ, λ and u 0 are defined as in a counting reward automaton. Each AAMDP induces an equivalent MDP ⟨Su 0 u 1 ⟨P A , [0], [1], 0⟩ ⟨P A , [1], [1], 0⟩ ⟨P B , [1], [0], 0⟩ ⟨¬P A ∧ ¬P B , [0], [0], 0⟩ ⟨¬P A ∧ ¬P B , [1], [0], 0⟩ ⟨P C , [1], [-1], 0⟩ ⟨P B , [1], [0], 0⟩ ⟨τ, [0], [0], 1⟩A , A A , T A , γ A , R A ⟩ with A A = A, γ A = γ, S A = S × {U ∪ F } × {1, ..., Γ} k , T A = P (⟨s ′ , u ′ , c ′ ⟩ | ⟨s, u, c ⟩, a) =    P (s ′ |s, a) if u ∈ F and u ′ = u, c ′ = c P (s ′ |s, a) if u / ∈ F and ⟨u ′ , c ′ ⟩ = δ(u, σ, Z(c)) 0 otherwise.and R A (s, a, s ′ ) = λ(u, σ, Z(c))(s, a, s ′ ), where σ := L(s, a, s ′ ).As the AAMDP is fundamentally an MDP, conventional reinforcement learning algorithms, such as Q-learning, may be used to compute a solution in the form of an optimal policy.Compatible Reward Functions As the CRA formulation is based on a counter machine, it is able to model both Markovian and non-Markovian reward functions to the extent that a Turing machine is able to distinguish between histories. This property holds as a two-counter counter automaton (equivalently, a two-stack pushdown automaton with a two-symbol alphabet) can simulate an arbitrary Turing machine (Hopcroft and Ullman 1995) .Relationship between Counting Reward Automata and Reward Machines Reward machines are a special case of the CRA formulation. The reward output function of a reward machine is dependent only on the current machine state. As a result, an RM output function is equivalent to that of a CRA which returns the same reward function for all transitions out of a given machine state. The RM state transition function is dependent only on the current machine state and the input symbol. Consequently, the state transition function is equivalent to that of a CRA which does not modify the value of its counters. Theorem 2. Any reward machine can be emulated by a CRA with an equivalent number of machine states and transitions.Proof. See Appendix.In this section, we discuss learning algorithms for the AAMDP formulation. As AAMDPs are fundamentally MDPs, we begin by discussing their compatibility with conventional reinforcement learning techniques. This is followed by the introduction of a novel learning algorithm for AAMDPs. This algorithm exploits task information encoded within the CRA of the AAMDP to increase sample efficiency. We provide pseudo-code implementations for the tabular case and discuss each algorithm's convergence guarantees.Each AAMDP is an MDP which takes into account the state of the CRA at each time step. As a result, the AAMDP agent not only considers the underlying ground environment state s when selecting an action, but also the CRA configuration ⟨u, c⟩. Regardless of this distinction, the construction satisfies the properties of an MDP. Consequently, any learning algorithm designed to learn policies for an MDP is compatible with the AAMDP formulation. Any convergence guarantees associated with such algorithms in MDPs hold by extension in AAMDPs. As these algorithms do not use automaton information when learning, it is unlikely that any increase in sample efficiency will be observed when they are applied to AAMDPs. To illustrate how a conventional reinforcement learning algorithm can be used with an AAMDP, we provide an adapted version of tabular Q-learning in the Appendix.We describe how task information encoded within the structure of a CRA can be used to enable more sample efficient learning. The learning algorithm we propose to exploit CRA task information is based on the Counterfactual experiences for Reward Machines (CRM) algorithm (Icarte et al. 2022) .Our algorithm has been adapted to support the k-counter counter machine used in the CRA formulation. The counterfactual experiences generated by this algorithm can be used to increase the sample efficiency of any off-policy learning method.We begin by providing an overview of the intuition behind the algorithm. We describe how task information, encoded within the automaton structure, can be used to enable more sample efficient learning. Suppose an agent in a ground environment state s takes action a, producing a subsequent state s ′ . If the CRA configuration was ⟨u, c⟩ prior to the transition, then the reward signal emitted by automaton would be r = λ(u, L(s, a, s ′ ), Z(c))(s, a, s ′ ). However, we are able to consider every possible machine configuration prior to the transition. This counterfactual reasoning generates a set of counterfactual experiences, each of which may be used for learning. The generation of synthetic experiences is enabled by the task information encoded within the automaton structure.In order to illustrate how counterfactual experiences can be incorporated into an off-policy learning algorithm, we present Counterfactual Q-Learning (CQL) in Algorithm 1. It can be seen that the only adaptation required is to the Qfunction update. That is, rather than updating the Q-function once based on the observed AAMDP transition, it is updated multiple times, considering every possible prior automaton configuration. The process begins with the agent executing an action and observing the next ground environment state (line 8). This information is passed to the labelling function to compute the input to the machine. This is followed by counterfactual experience generation. That is, we simulate what would have happened had the machine been in any of its non-terminal configurations when the transition took place (lines 9-10). For each experience, the corresponding next machine configuration and reward are computed (lines 11-12) . This information is used to update the Q-function (lines 13-17). Finally, the machine configuration is updated based on the transition that was observed in reality. We note that in practice, the loop on line 10 can be optimised by maintaining a cache of observed counter states.Theorem 3. Given an AAMDP M, tabular CQL converges to an optimal policy for M in the limit (under the same conditions required for convergence of Q-learning in MDPs).Proof. As the counterfactual experiences generated in CQL are sampled according to the transition probability distribution P (⟨s ′ , u ′ , c ′ ⟩ | ⟨s, u, c ⟩, a) = P (s ′ |s, a), the convergence proof provided by Watkins and Dayan (1992) for tabular Q-learning applies directly to the case of CQL.Algorithm 1: Counterfactual Q-Learning (CQL) Input: AAMDP M = ⟨S A , A A , T A , γ A , R A ⟩ Output: Optimal Q-value function Q * 1: Initialise Q(s, u, c, a) ← 0 ∀ ⟨s, u, c, a⟩ ∈ S A × A A 2: repeat 3: Initialise u ← u 0 4: Initialise c ← 0 5:Initialise s as initial environment state 6: while u / ∈ F and s non-terminal do 7:Sample a from ⟨s, u, c⟩ using policy derived from Q (e.g. ϵ-greedy)8:Execute action a, observe s ′ 9:for u i ∈ U do 10:for c j ∈ {1, ..., Γ} k do 11:⟨u k , c k ⟩ ← δ(u i , L(s, a, s ′ ), Z(c j )) 12: r k ← λ(u i , L(s, a, s ′ ), Z(c j )) 13: if u k ∈ F or s ′ is terminal then 14: Q(s, u i , c j , a) α ← r k 15: else 16: Q(s, u i , c j , a) α ← r k + γ max a ′ ∈A Q(s ′ , u k , c k , a ′ ) 17: end if 18:end for 19:end for20: Compute ⟨u ′ , c ′ ⟩ ← δ(u, L(s, a, s ′ ), Z(c)) 21: Set u ← u ′ 22: Set c ← c ′ 23:end while 24: until endIn this section, we provide an empirical evaluation of the proposed methods. We begin by considering a context-free task specification that cannot be expressed by current statemachine-based approaches. In the following experiment, we compare the sample efficiency of our approach to that of state-of-the-art techniques for a context-sensitive task. Finally, we demonstrate how expert knowledge is naturally integrated into our formulation during task specification. An LLM is used to specify the desired task as a regular language which is used to produce the required automaton. A solution is obtained through function approximation.We use the previously described LetterEnv environment to evaluate our methods on a task specification only expressible as a context-free language. The environment is illustrated in Figure 1 . The agent is required to observe a sequence of environment symbols corresponding to a task in the contextfree language L = {A N BCD N : N ∈ N}. In our experiments, we compare CRA performance to that of state-ofthe-art RM-based learning approaches (Icarte et al. 2022) , including CRM and CRM with automated reward shaping (CRM+RS). For each approach, we compute the number of environmental interactions required to learn a policy which solves the task. The results are shown in Figure 3 . As the CRA is able to model the CFL reward directly, one machine can be trained and immediately used to solve all tasks in the specification. This is not true for the RM formulation, which is limited to the expression of reward functions in regular languages. This requires the RM formulation to emulate a CRA. This is achieved through the use of separate RMs for each value of N . Notably, while the CRA configuration remains constant across all tasks, the number of states required by an RM grows linearly with task complexity. The results demonstrate that the ability of the CRA to directly model more complex reward functions provides significant improvements in sample efficiency in comparison to CRA emulation through a collection of RMs.We consider the Office Gridworld environment illustrated in Figure 4 . We focus on a task specification that is only expressible as a context-sensitive language. The following task specification is used for this experiment. Firstly, the agent is required to navigate to the mail room and collect all available mail (the amount of mail is randomly generated at the start of each episode). The agent must then make a single coffee for each person that it has collected mail for. Finally, the mail and coffee must be delivered to the office employees located at P . The agent immediately fails the task if a decoration is broken or an incorrect number of coffees is collected/delivered. This task requires the agent to remember both the amount of mail it has collected as well as the number of coffees it has made. As a result of this property, this task can only be represented as a context-sensitive language. Due to the memory requirements associated with this task, two counter variables are used in the CRA formulation. For this task specification, we note that the CRA formulation, trained with the CQL algorithm, converges to a solution significantly faster than both CRM and CRM with automated reward shaping (CRM+RS) in all cases (see Appendix). However, we focus on the complexity of the state machines produced by either of the approaches. The CRA required to solve the task consists of three intuitive nonterminal states. These states correspond to the tasks: (i) collect all mail; (ii) make coffee and (iii) deliver the collected items. As the reward machine formulation is based on a finite state machine, it is unable to directly express task specifications corresponding to non-regular languages. This requires the reward machine to contain a single state for each CRA task-counter pair. We note that as the CRA formulation is able to express the context-sensitive task specification directly-it is therefore able to solve all task strings in Figure 5 : Comparison between the complexity of the state machines produced by the CRA and RM formulations. The illustration shows the complexity of the machine required to solve a task specification with a fixed upper bound on task-string length (in this case, the maximum number of mail items). RMs were constructed using a general template implementation parameterised by the maximum string length required for the task.the language without modification. This is illustrated in Figure 5 , with the machine configuration remaining constant as the maximum length of a task string is increased. An illustration of the state machines is provided in the Appendix. As existing approaches assume that the automaton is given, this requires that the specification of machines is intuitive and human-readable. We note that this is not the case. Complex algorithms were required to generate the RMs used in these experiments. The state machines required by current approaches are not only difficult to specify, but also to verify for correctness.We now illustrate how expert knowledge can be naturally integrated into our formulation. We make use of the Office Gridworld environment to demonstrate our approach. We consider the following task specification. The agent is required to collect exactly one item of mail and deliver it to a person without breaking a decoration. The natural language description of this task is converted to a formal language through the use of an LLM, specifically ChatGPT (Ope-nAI 2023). The LLM is prompted to produce a formal language that specifies the sequence of high-level events satisfying the task description. This formal language description is used to produce the required automaton illustrated in In recent years, formal language and state machine-based approaches for task specification and efficient learning have been extensively studied (Littman et al. 2017; Li, Vasile, 2019) and learning the abstract machines from data like in Abadi and Brafman (2020) . However, due to current formulations' dependence on Finite State Machines (FSMs), they are significantly limited in terms of the types of reward functions they are able to express. This restricts the application of such methods to the small subset of problems which may be represented as Regular Decision Processes (RDPs) (Brafman, De Giacomo et al. 2019) . This property imposes significant constraints on the classes of problems expressible by current approaches. For example, any problem which involves counting the number of times a state has been reached cannot be solved using these methods. Finally, a related number of works have been proposed under the HRL framework for solving temporally extended tasks (Barto and Mahadevan 2003; Barreto et al. 2019) . Solutions include methods such as the options framework (Sutton, Precup, and Singh 1999) , HAMs (Parr and Russell 1997) and MAXQ (Dietterich 2000) . Levy et al. (2017) make use of goal-conditioned policies at multiple layers of the hierarchy for RL. However, all of these approaches have been shown to struggle with exploration (Kulkarni et al. 2016 ) and reward definition (Eysenbach et al. 2018 ) which has limited their application.We have proposed the counting reward automata formulation as a universal approach to modelling reward in reinforcement learning systems. As a result of the formulation's dependence on counter machines, it is able to model reward functions expressible in any formal language, unlike previous approaches. Task information is encoded within the abstract machine during the reward modelling process, which may be exploited to enable more sample-efficient learning. Given a counting reward automaton for a task of interest, we have proposed a learning algorithm that can exploit the automaton structure to increase sample efficiency through counterfactual reasoning. The convergence guarantees of this approach have been discussed in the tabular case. Through empirical evaluation, we demonstrate the effectiveness of the proposed formulation both in terms of sample efficiency as well as state machine complexity. Finally, we have demonstrated how expert knowledge can be integrated into the formulation through the use of natural language task descriptions and LLMs. 
 
 Appendix:  



Reviews: review: title: title: Review
main_review: main_review: This paper introduces a novel finite state machine variant called Counting Reward Automaton (CRA), capable of modeling any reward function expressible as a formal language. This mitigates the limitations of existing approaches that they can only handle regular language expressions, whereas this work permits the use of unrestricted grammar. Hence, this framework can handle a larger set of tasks than the existing works. The authors have also demonstrated that this framework supports using LLM-based formal language definitions from natural language task descriptions.

Strengths:
* This paper is well-written and well-explained.
* The CRA automata is novel and can model reward functions expressible as recursively languages.
* This paper also represents a sample efficient learning technique.
* The framework also supports the use of LLM to translate the NL task description into a formal language.

Weaknesses:
* Even if this paper demonstrates a very strong theoretical analysis of the contributions. However, it has lack of empirical studies to showcase the benefits.
* Interested to see how ChatGPT can be used to generate formal language specification from NL? what are the limitations? Very less amount of details have been provided. What kind of quality has been performed over automatic FL generation using ChatGPT?
title: title: Interesting ideas, less informative empirical evidence
main_review: main_review: ### **Summary**
The paper presents counting reward automata (CRA), a novel framework for modeling reward functions in reinforcement learning (RL) as formal languages. The paper shows that CRA can express any recursively enumerable reward function, unlike previous state machine-based approaches limited to regular languages. The paper also proposes Counterfactual Q Learning that exploits the structure of CRA to improve sample efficiency and convergence guarantees. It demonstrates their effectiveness on complex tasks that require long-horizon planning and counting.
The paper’s strengths are:
It introduces a general and expressive framework for reward function specification that can handle a wide range of problems, including context-free and context-sensitive languages.
It provides theoretical and empirical evidence that CRA can improve the performance and scalability of RL agents compared to existing methods.

### **Strengths**
- General and expressive framework for reward function specification that can handle a wide range of problems, including context-free and context-sensitive languages.
- Comprehensive theoretical and empirical evidence that CRA can improve the performance and scalability of RL agents compared to existing methods.
- Leveraging natural language and large language models to facilitate the intuitive and human-readable specification of CRA from task descriptions.

### **Weakness**
- Lacking clear comparison or discussion of the trade-offs between CRA and other neuro-symbolic or hierarchical RL methods that also aim to address long-horizon tasks.
- Missing analysis or evaluation of the robustness, generalization, or interpretability of CRA-based agents.
- Somewhat toy examples
title: title: Interesting paper, but less detailed information
main_review: main_review: Pros:
1. This paper presents an agent equipped with such an abstract machine is able to solve a larger set of tasks than those utilizing current approaches. Unlike previous approaches, which are limited to the expression of tasks as regular languages.
2. This paper shows that the state machines required in their formulation can be specified from natural language task descriptions using large language models. Empirical results demonstrate that their method outperforms competing approaches in terms of sample efficiency, automaton complexity, and task completion.

Cons:
1. The version of ChatGPT been used for evaluating in the paper did not been clearly mentioned. The experiment results in terms of sample efficiency from Figure 6 did not show explicitly better than the other baseline methods.
2. The experiment details include the description for the dataset such as train/dev/test sets, the name of the dataset, a detailed description or example for counterfactual reasoning are missing. Figure 6 says the mean and variance were reported over 10 independent trials. A confidence interval will be needed in this case.