{'fraction_non_alphanumeric': 0.05198096847347592, 'fraction_numerical': 0.006625461336653475, 'mean_word_length': 3.9723634755693125, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Regret Analysis in Deterministic Reinforcement Learning

We consider Markov Decision Processes (MDPs) with deterministic transitions and study the problem of regret minimization, which is central to the analysis and design of optimal learning algorithms. We present logarithmic problem-specific regret lower bounds that explicitly depend on the system parameter (in contrast to previous minimax approaches) and thus, truly quantify the fundamental limit of performance achievable by any learning algorithm. Deterministic MDPs can be interpreted as graphs and analyzed in terms of their cycles, a fact which we leverage in order to identify a class of deterministic MDPs whose regret lower bound can be determined numerically. We further exemplify this result on a deterministic line search problem, and a deterministic MDP with state-dependent rewards, whose regret lower bounds we can state explicitly. These bounds share similarities with the known problem-specific bound of the multi-armed bandit problem and suggest that navigation on a deterministic MDP need not have an effect on the performance of a learning algorithm.


I. INTRODUCTION
Reinforcement Learning addresses the optimal control problem of an unknown dynamical system, which is traditionally modeled as a Markov Decision Process (MDP). The stochastic nature of this problem induces an explorationexploitation dilemma where the decision-maker must balance between decisions which give insight into the dynamics of the system and decisions which, given the information available, are considered optimal. This dilemma is quantified mathematically by the notion of regret, defined as the difference between the cumulative reward obtained by the decision maker, and that obtained by an oracle who always makes the best decisions.
The design of an optimal algorithm is then equivalent to the design of an algorithm that minimizes regret. A natural question then is, what is the minimum regret that can be achieved by a learning algorithm, given a certain class of MDPs. The answer to this question is expressed in the form of problem-specific regret lower bounds. By problemspecific, we mean that there is an explicit dependence on the system parameter. In contrast with minimax bounds which are conservative in nature, these bounds accurately quantify the fundamental performance limits attainable by a learning algorithm. Moreover, they are instrumental in the design of optimal learning algorithms, as has been evidenced by [1], [2], and [3]. In this work we study the fundamental performance limits for a class of MDPs with finite state-action spaces and deterministic transitions. The reward obtained with each transition is stochastic and must be learned by the decision-maker. Knowledge of the transitions can be interpreted as knowledge of the structure of the problem, and so we are inspired by [4] and [3] who quantify the possible performance gains when the structure of their respective problems is exploited.

A. Related Work
The first asymptotic, logarithmic, and problem-specific regret lower bound for MDPs was provided, for the case of known rewards, by [5] who also devised an algorithm whose regret upper bound asymptotically matches their lower bound. This lower bound is extended by [3] to the case of unknown rewards as well as the case of MDPs with structure. For both cases, [3] propose an algorithm with matching regret upper bounds.
The case of communicating MDPs is addressed by the works of [6], [7], [8], and [9]. They provide logarithmic and finite-time regret guarantees, but at the expense of optimality, i.e., a much larger constant in front of log T .
To the best of our knowledge, regret minimization for deterministic MDPs has only been addressed by [10]. Therein, they propose UCYCLE, an extension of the UCB1 algorithm [11] which selects optimistically among cycles of state-action pairs. While the algorithm is claimed to achieve logarithmic regret, it does not match their proposed minimax lower bound and the analysis of the algorithm is based on a relaxed notion of regret.

B. Contributions
In this work, we present a problem-specific asymptotic regret lower bound valid for any MDP with deterministic transitions and any learning algorithm.
By relating deterministic MDPs to graphs and analyzing them in terms of their cycles, we identify a class of deterministic MDPs whose cycles are disjoint. These problems possess a decoupling property which allows us to simplify our lower bound considerably from an infinite-dimensional optimization problem, to two nested finite-dimensional ones, making it possible to evaluate it numerically.
We exemplify our simplified bound on two specific problems, that of deterministic line search and that of deterministic MDPs with state-dependent rewards. For both problems, we are able to solve the optimization problems associated with their lower bounds analytically and thus state them explicitly. These bounds are analogous to the lower bound derived by Lai and Robbins [12] for the multi-armed bandit problem, a fact which suggests that they are tight. This also indicates that an optimal algorithm need not experience additional regret resulting from navigating a deterministic MDP.

II. PROBLEM FORMULATION
In this section we introduce Deterministic Markov Decision Processes and define precisely the notion of regret. We then present relevant graph-theoretic notation which we will use in our study of regret lower bounds.

A. Deterministic Markov Decision Processes
We denote by Φ D the set of all Deterministic Markov Decision Processes (DMDPs), which consists of discretetime controlled Markov Chains with deterministic transitions. A DMDP is defined as the quadruple φ = (S, A, p φ , q φ ), where S is the finite state space and A is a finite set of actions. They have respective cardinalities S and A. Given a state s and an action a, a transition to the next state s ′ occurs with probability p φ (s ′ |s, a) = 1. A random reward is also sampled from a one-parameter exponential distribution q φ (·|s, a), parameterized by its mean r φ (s, a). A decision maker chooses actions according to a policy π, defined as a distribution over A based on the history of states, actions, and rewards. We denote by Π the set of all policies. A notable subset, is the set of all stationary, deterministic, Markov policies Π D , which is the set of mappings π : S → A.
Given a DMDP, the expected cumulative reward up to time step T obtained by the decision maker who follows a policy π ∈ Π from the initial state s is V π T (s) = E π s T t=1 r φ (s t , a t ) . Here, E π s [·] is the expectation under policy π given that s 1 = s. The objective of the decisionmaker, when faced with an unknown DMDP φ, is to devise a policy π ∈ Π that maximizes V π T (s) or, equivalently, minimizes the regret up to time T : R π T (s) : A DMDP φ is communicating if for any pair of states s, s ′ ∈ S there exists π ∈ Π D such that s ′ is accessible from s. For any communicating φ and any policy π ∈ Π D , we denote by g π φ (s) the gain of π with initial state s: g π φ (s) := lim T →∞ 1 T V π T (s), which is known to always exist in this problem setting (see Proposition 8.1.1 in [13]). We denote by Π ⋆ (φ) the set of gain-optimal (or optimal) policies, i.e., the stationary policies with maximal gain: It is known (see Theorem 8.3.2 in [13]), that if φ is communicating then the maximal gain, denoted by g ⋆ φ , is constant.

B. Graphs and Cycles
We associate a DMDP with a graph G = (V, E) where the states are the vertices, V = S, and the state-action pairs are the edges, E = S × A. A walk is defined as a tuple of edges ((s 1 , a 1 ), . . . , (s p , a p )) such that p φ (s i+1 |s i , a i ) = 1 for 1 ≤ i < p. Given two walks U = (u 1 , . . . , u p ) and W = (w 1 , . . . , w q ), we define their concatenation U · W = (u 1 , . . . , u p , w 1 , . . . , w q ). A path is a walk without repeated vertices.
A walk or path is closed if the its final edge connects to its initial vertex, i.e., p φ (s 1 |s p , a p ) = 1. A closed walk is referred to as a cycle, while a closed path is referred to as a simple cycle. Since the DMDPs we consider are finite, there exists a finite number of simple cycles in any given DMDP φ (up to a permutation). We denote the set of all such simple cycles by C.
In a DMDP φ with initial state s, every stationary deterministic policy π ∈ Π D induces a cycle C π φ (s). The gain of this policy can be written as: Since the gain of a gain-optimal policy does not depend on the initial state, it follows that for any π ∈ Π ⋆ (φ) there exists an optimal cycle C such that: More importantly, if such an optimal cycle exists, then there also exists an optimal simple cycle with the same gain: if there exists a gain-optimal policy π that induces an optimal cycle C, then there also exists a gain-optimal policy π ′ that induces an optimal simple cycle C ′ .
Proof. The proof consists of two parts. Firstly, we show that any cycle C can be expressed as the concatenation of simple cycles C i , up to a permutation. Secondly, we show that if C is gain-optimal, then one of its components C i must also be gain-optimal. As shown in [14], we can express any walk C as the concatenation of possibly empty paths W i and simple cycles C i ∈ C, i.e, C = C 1 · W 1 . . . C q · W q . We define by C 1 := W 1 · W 2 . . . W q the resulting sequence of edges after we have removed every simple cycle C i . Then C 1 is also a cycle and thus can also be decomposed into simple cycles and possibly empty paths. We recursively apply this decomposition and removal step on each cycle C i such that iteration C N is empty. We then have where m i is the number of times the simple cycle C i appears in cycle C, and n is the cardinality of C. We thus have: which, lettingC := {C i ∈ C : m i = 0}, leads to: However, since g φ (C) is the optimal gain, we must have that , for all C i ∈ C. Therefore, the following equality holds: Thus, for a gain-optimal policy π which induces cycle C, there exists a simple cycle C ′ = argmax Ci∈C g φ (C i ), induced by a policy π ′ , which is also gain-optimal. As a consequence of this proposition, we will be restricting our attention to simple cycles and will henceforth abuse the notation by referring to them as cycles.
III. REGRET LOWER BOUND FOR DETERMINISTIC MARKOV DECISION PROCESSES In this section, we state our regret lower bound valid for any communicating DMDP. To this aim, we introduce the following definitions and notations: the Kullback-Leibler divergence between the reward distributions q φ and q ψ at state s when action a is chosen: Definition 2. We define by ∆(φ) the set of confusing models for DMDP φ. Specifically, ψ is confusing if it is absolutely continuous with respect to φ, (i) has the same reward distributions at every state-action pair that is part of the optimal cycle of φ and (ii) has optimal policies that are not optimal under φ, i.e., Finally, we denote by N T (s) and N T (s, a), the respective number of times, up to time T , that the state s and stateaction pair (s, a) have been visited. Theorem 1. Let π ∈ Π be a uniformly good policy. For all φ ∈ Φ D and initial s 1 ∈ S we have: where C(φ) is the value of the optimization problem: with information constraints: and navigation constraints: Proof. The proof relies on two propositions which we introduce below. The first is an expression of regret as the sum of the number of times every sub-optimal state-action pair has been visited, first shown by [15]: For any policy π ∈ Π and any initial state s 1 ∈ S, we have, as T → ∞: The second proposition is the result of a fundamental information inequality by [16] and first adapted to MDPs by [3]: , and any event E: Note that in the above sum, we do not consider (s, a) ∈ C ⋆ φ since, by the definition of ψ, we have KL φ|ψ (s, a) = 0 if (s, a) ∈ C ⋆ φ . Now we select event E, taking advantage of the fact that π is uniformly good. By definition of ψ, we have Π(φ) ∩ Π(ψ) = ∅, which implies that there exists (s, a) ∈ C ⋆ φ \C ⋆ ψ such that, for all α > 0, We fix a state-action pair (s, a) and note that s is recurrent under an optimal policy for φ, so there exists ρ > 0 such that E π φ|s1 [N T (s)] = ρT for large enough T . We now define the event E as: An application of Markov's inequality then yields It follows that P π φ [E] → 0 and P π ψ [E] → 1, as T → ∞. Therefore, we get: , whose left-hand side converges to 1 as T → ∞ as a consequence of our choice of (s, a). Substituting this result in (5) yields: This inequality, combined with Proposition 2, yields the optimization problem along with the information constraints (3). The navigation constraints (4) follow directly from the deterministic transitions of problem φ.
Theorem 1 quantifies the minimal number of times a sub-optimal state-action pair (s, a) must be visited by any uniformly good policy. This number scales as η ⋆ (s, a) log T where η ⋆ (s, a) is the solution to the optimization problem (1) and thus implicitly defines the regret lower bound. The constraint sets I(φ) and N (φ) are respectively referred to as the information and navigation constraints. The former constrain the minimum number of visits on (s, a) to discern between the problem φ and every confusing parameter ψ while the later constraint the number of visits as a result of the transition dynamics.

IV. REGRET LOWER BOUNDS FOR DISJOINT CYCLES
A notable limitation of Theorem 1 is that the optimization problem (2) is infinite dimensional (as a consequence of the information constraint set I(φ). However, it can be simplified to a finite-dimensional one in the case of DMDPs where every cycle in C is disjoint. First, we note that ∆(φ) = ∪ C∈C ∆(C; φ), where we define ∆(C; φ) as the set of bad problems such that the cycle C is optimal, i.e., Decoupling of information constraints. Our aim is to reduce the dimension of the information constraints (3). To this end, we first decouple them by expressing the information constraint set as: so that for each cycle C there exists a set of constraints that must be satisfied by the solution of (2). Every cycle can be associated to a maximally confusing parameter ψ, obtained by solving, for any η(s, a) and a fixed C, the following optimization problem: Using the fact that all cycles C are disjoint, the solution to (6) is obtained by a ψ that satisfies: (i) g ψ (C) = g ⋆ φ ; (ii) KL φ|ψ (s, a) = 0, ∀(s, a) / ∈ C. This observation leads to the following constraint set: Intersection of navigation and information constraints. We now examine the navigation constraints in (4). Consider H π T = (s 1 , a 1 , s 2 , a 2 , . . . , s T , a T ), which is a trajectory induced by a policy π ∈ Π starting at state s 1 up to time T . For any DMDP φ, this trajectory is an open walk in a graph, and so it can be decomposed into a (possibly empty) set of cycles C ∈ C and a finite path P [17]. We denote by N T (C), the number of times a cycle C appears in the decomposition of H π T . By definition, all cycles in φ are disjoint, and so, for all uniformly good policies, and for any state-action pair (s, a) ∈ C = C ⋆ φ , we have Thus, for uniformly good policies, the navigation constraints in (4) imply that every state-action pair in a cycle C must be sampled at the same rate. In light of this observation, the information constraint set can be rewritten as: Now, recall that q φ (s, a) belongs to the one-parameter exponential distribution family parameterized by the mean r φ (s, a). Then, as explained in [1], there exists a convex, twice differentiable function b sa (φ) such that r φ (s, a) = b sa (φ). The Kullback Leibler divergence then becomes: s, a)).
Thus we can rewrite (6) as an optimization problem with respect to the mean reward vector r ψ : Finally, to simplify notation, we define the set of mean rewards that satisfy (8) as: The above simplifications lead to the following regret lower bound that is valid for any DMDP φ with disjoint simple cycles: Theorem 2. Let π ∈ Π be a uniformly good policy. For all φ ∈ Φ D with disjoint cycles, and initial s 1 ∈ S we have: where C(φ) is the value of the optimization problem: with information constraints: KL(r φ (s, a), r ψ (s, a)) ≥ 1 , and navigation constraints: Theorem 2 shares the same interpretation as Theorem 1 with the notable difference that we now have two finitedimensional nested convex optimization problems which can be solved efficiently. In order to determine the lower bound, we must first solve (7) for each cycle C. Each solution corresponds to the most confusing parameter ψ with the property that its associated cycle is optimal. Together they form |C| constraints which, combined with the |C| navigation constraints (12) comprise the set of constraints for the regret minimization problem (10).

V. EXAMPLES
In this section we present two example applications that can be modeled as DMDPs with disjoint cycles and for which we can state the regret lower bound explicitly. We also highlight the relationship between DMDPs with disjoint cycles and the multi-armed bandit problem.
As we can see, this DMDP consists of n cycles C i = ((s i , a 1 ), (s i+1 , a 2 )) for i ∈ {1, . . . , n}. For every such deterministic line search problem φ, each cycle C i has gain Denote by C j = C ⋆ φ the optimal cycle for φ. We first express the set of bad parameters ∆(φ) as a union over the sets ∆(C i ; φ): Then, the set of navigation constraints is simply: The information constraints can be found by solving for every cycle C i , the following convex optimization problem: This problem can be solved analytically, with its solution satisfying the pair of equations: Using this solution, we can define the information number of cycle C i as and we attain the following information constraint set: In light of (13) and (14), we can rewrite the optimization problem (9) as: with solution η ⋆ (C i ) = 1/I(C i ). This leads to the explicit regret lower bound: Corollary 1. Let π ∈ Π be a uniformly good policy. For all deterministic line search problems φ and initial s 1 ∈ S we have: In contrast to Theorems 1 and 2, the lower bound in Corollary 1 is explicit and analogous to (15) which corresponds to the problem-specific lower bound for the multi-armed bandit problem. Treating g φ (C i ) as the reward of the cycle C i and the information number I(C i ) as a similarity metric between the rewards of the cycle C i and those of the optimal cycle, we can interpret the deterministic line search problem as a case of multi-armed bandit where each cycle is an arm.

B. State-dependent Rewards
We now consider DMDPs with state-dependent rewards, i.e, DMDPs φ ∈ Φ D with reward distributions q φ (s) having mean r φ (s). Because of the deterministic structure, this is equivalent to having the same reward distribution for every state-action pair that leads to the same state. That is, for any two state-action pairs (s 1 , a 1 ), (s 2 , a 2 ) that satisfy p φ (s ′ |s 1 , a 1 ) = p φ (s ′ |s 2 , a 2 ) = 1, for a state s ′ , it holds that q φ (·|s 1 , a 1 ) = q φ (·|s 2 , a 2 ) := q φ (·|s ′ ). We further assume that it is always possible to stay in the same state, i.e., there exists a ∈ A such that p φ (s|s, a) = 1. Actions that lead to the same state can be treated as identical, and thus the new action set becomes A = S. An example of such a problem is given in Figure in 2.
For any state-dependent reward problem φ, we define the optimal state as s ⋆ φ = argmax s∈S r φ (s) and its associated optimal mean reward as r ⋆ φ = r φ (s ⋆ φ ). Let N T (s|s ′ ) be the number of times state s has been chosen from state s ′ up to time T and let N T (s) = s ′ ∈S N T (s|s ′ ) be the total number of times s has been visited. Similarly, we define η(s|s ′ ) = E[N T (s|s ′ )] log T and η(s) = E[N T (s)] log T . For every state s we define its set of predecessors P(s) := {s ′ ∈ S : s ∈ A(s ′ )} and its set of descendants D(s) := {s ′ ∈ S : s ′ ∈ A(s)}.
We now show that in problems with state-dependent rewards, we recover the multi-armed-bandit setting, and our bound matches that of Lai and Robbins [12]. This has two important implications. Firstly, that our lower bound is attainable (tight) and secondly, that it is possible to devise an optimal algorithm whose regret due to navigating a DMDP is sub-logarithmic (otherwise, there would be an added term on the regret due to navigation). Corollary 2. Let π ∈ Π be a uniformly good policy. For all DMDPs φ with state-dependent rewards and initial s 1 ∈ S we have: Proof. First observe that, as a consequence of our definitions above, we can rewrite (2), (3), and (4) as follows: subject to Where we use the fact that, since it is always possible to stay in the same state, we will have C ⋆ φ = {s ⋆ φ } and thus g ⋆ φ = r ⋆ φ . As a consequence, we can restrict our attention to cycles consisting of a single state, so that the set of bad parameters becomes ∆(φ) = ∪ s =s ⋆ φ ∆(s; φ), defined for every s ∈ S, In words, the set of bad parameters ψ where the reward distribution at s ⋆ φ is unchanged and a new state s becomes optimal.
It suffices to verify that this solution satisfies the navigation constraints (18). Indeed, we have, for all s ∈ S, η(s) = Where the first equality follows from the definition of η(s), the second from the observation that η(s|s ′ ) = 0, ∀s ′ / ∈ P(s), and the last equality from (18).
Finally, since it is always possible to stay in the same state, we can let η(s) = η(s|s) for every s ∈ S. Essentially, the exploration rates every state are decoupled, which complies with the solution η ⋆ (s).

VI. CONCLUDING REMARKS
For the case of communicating MDPs with deterministic transitions, we presented a general asymptotic regret lower bound that is problem specific and has the form of an infinite dimensional linear program. We focused on the case of DMDPs with disjoint cycles, and showed that this problem class has a decoupling property that allows us to simplify the regret lower bound by reducing it to two nested finite-dimensional linear programs. We exemplified this result by presenting the deterministic line search problem as well as DMDPs with state-dependent rewards. For these, we solved the associated optimization problems analytically and identified their similarities with the multi-armed bandit problem.
Notably, the fact that our lower bound matches that of Lai and Robbins [12] points to the surprising and counterintuitive result that we need not experience additional regret due to navigation.