The E ect of Representation and Knowledge on Goal-Directed Exploration with Reinforcement-Learning Algorithms: The Proofs

This technical report contains the proofs of all theorems that are central to our Machine Learning Journal article \The E ect of Representation and Knowledge on GoalDirected Exploration with Reinforcement-Learning Algorithms," in which we analyze the complexity of on-line reinforcement-learning algorithms that are applied to goaldirected exploration tasks: Previous work had concluded that, even in deterministic state spaces, initially uninformed reinforcement learning was at least exponential for such problems, or that it was of polynomial worst-case time-complexity only if the learning methods were augmented. In the article we prove that, to the contrary, the algorithms are tractable with only a simple change in the reward structure (\penalizing the agent for action executions") or in the initialization of the values that they maintain. In particular, we provide tight complexity bounds for both Watkins' Q-learning and Heger's Q-hat-learning and show how their complexity depends on properties of the state spaces. We also demonstrate how one can decrease the complexity even further by either learning action models or utilizing prior knowledge of the topology of the state spaces. Our results provide guidance for empirical reinforcement-learning researchers on how to distinguish hard reinforcement-learning problems from easy ones and how to represent them in a way that allows them to be solved e ciently. This technical report contains the proofs of the theorems used in our Machine Learning Journal article \The E ect of Representation and Knowledge on Goal-Directed Exploration with Reinforcement-Learning Algorithms" that we have not already proved there. The report uses the terminology and de nitions described in that article. We assume that all state spaces are safely explorable and (without loss of generality) that all states that cannot be reached from the start state or that can only be reached by passing through a goal state have been deleted. First, we prove several properties of consistent Q-values, for example how they relate to admissible Q-values. We prove properties of admissible Qor Q̂-learning in deterministic state spaces if the initial Q-values are consistent. Then, we show that the same properties hold for admissible Q̂-learning in non-deterministic state spaces (which include deterministic state spaces as a special case) if the initial Q-values are admissible. Finally, we prove our complexity results. All proofs are for the undiscounted case with action-penalty representation. The transformations of the Q-values that we have described in Sections 6.1.1.2. or 6.1.2. of the article can then be used to transfer the results to discounted Qor Q̂-learning with action-penalty representation or goal-reward representation, respectively. The time superscripts t used in the following refer to the values of the variables immediately before the agent executes the (t+ 1)st action. Theorem 1 If Q-values are consistent for undiscounted Qor Q̂-learning with actionpenalty representation, then mins02X d(s; s) U(s) 0 for all s 2 S, where X := fs 2 S : U(s) = 0g. Proof by induction on d(s) := mins02X d(s; s). Note that d(s) is nite for all s 2 S, since the state space is safely explorable and G X. If d(s) = 0, then s 2 X and therefore U(s) = 0. Thus, d(s) = U(s) = 0. If d(s) 6= 0, then s 62 X G and therefore s 2 S n G. Let a := argmina02A(s)maxs02succ(s;a0) d (s). Assume that the theorem holds for all s 2 S with d(s) < d(s). Then, it holds for all s 2 succ(s; a), since maxs02succ(s;a) d (s) = d(s) 1 < d(s) and therefore d(s) < d(s). Thus, d(s) = 1 maxs02succ(s;a) d (s) Assumption 1 + mins02succ(s;a) U(s ) Consistency Q(s; a) maxa02A(s)Q(s; a ) = U(s) maxs02S;a02A(s)Q(s ; a) Consistency 0. Theorem 2 If Q-values are consistent for undiscounted Qor Q̂-learning with actionpenalty representation, then 1 maxs02succ(s;a)mins002X d(s ; s) Q(s; a) 0 for all s 2 S nG and a 2 A(s), where X := fs 2 S : U(s) = 0g.