Direct Code Access in Self-Organizing Neural Networks for Reinforcement Learning

1 Introduction

Reinforcement learning [Sutton and Barto, 1998] is an interaction based paradigm wherein an autonomous agent learns to adjust its behaviour according to feedback from the environment. Classical solutions to the reinforcement learning problem generally involve learning one or more of the following mappings, the first linking a given state to a desired action (action policy), and the second associating a pair of state and action to a utility value (value function), using temporal difference methods, such as SARSA [Rummery and Niranjan, 1994] and Q-learning [Watkins and Dayan, 1992]. The problem of the original formulation is that mappings must be learned for each and every possible state or each and every possible pair of state and action. This causes a scalability issue for continuous and/or very large state and action spaces.

Neural networks and reinforcement learning have had an intertwining relationship [Kaelbling et al., 1996]. In particular, multi-layer feed-forward neural networks, also known as multi-layer perceptron (MLP), have been used extensively in many reinforcement learning system and applications [Ackley and Littman, 1990; Sutton, 1984]. Under the recent thread of research in Approximate Dynamic Programming (ADP) [Si et al., 2004], MLP and gradient descent backpropagation (BP) learning algorithms are commonly used to learn an approximation of the value function from the state and action spaces (value policy) and/or an approximation of the action function from the state space (action policy). MLP and BP however are not designed for online incremental learning as they typically require an iterative learning process. In addition, there is an issue of instability in the sense that learning of new patterns may erode the previously learned knowledge. Consequently, the resultant reinforcement learning systems may not be able to learn and operate in real time.

Instead of learning value functions and action policies, self-organizing neural networks, such as Self-Organizing Map (SOM), are typically used for the representation and generalization of continuous state and action spaces [Smith, 2002]. The state and action clusters are then used as the entries in a Q-value table implemented separately. Using a localized representation, SOM has the advantage of more stable learning, compared with backpropagation networks. However, SOM remains an iterative learning system, requiring many rounds to learn the compressed representation of the state and action patterns. In addition, as mentioned in Smith (2002), SOM is expected to scale badly if the dimensions of the state and actions spaces are significantly higher than the dimension of the map. As such, most applications of SOM are limited to low dimensional state and action spaces.

A recent approach to reinforcement learning builds upon Adaptive Resonance Theory (ART) [Carpenter and Grossberg, 1987], also a class of self-organizing neural networks, but with very distinct characteristics from SOM. Ueda et. al (2005) use ART models to learn the clusters of state and action patterns. The clusters are in turns used as the compressed states and actions by a Q-learning module. Ninomiya (2002) couples a supervised ART system with a Temporal Difference reinforcement learning module in a hybrid architecture. Whereas the states and actions in the reinforcement module are exported from the supervised ART system, the two learning systems operate independently. The redundancy in representation unfortunately leads to instability and unnecessarily long processing time in action selection as well as learning of value functions. Through a generalization of ART from one input pattern field to multiple pattern channels, Tan (2004) presents a neural architecture called FALCON (Fusion Architecture for Learning, COgnition, and Navigation), that learns multi-channel mappings simultaneously across multimodal input patterns, involving states, actions, and rewards, in an online and incremental manner. For handling problems with delayed evaluative feedback (reward signal), a variant of FALCON, known as TD-FALCON [Tan and Xiao, 2005], learns the value functions of the state-action space estimated through Temporal Difference (TD) algorithms. Compared with other ART-based systems described by Ueda et. al and Ninomiya, TD-FALCON presents a truly integrated solution in the sense that there is no implementation of a separate reinforcement learning module or Q-value table.

Although TD-FALCON provides a promising approach, its action selection procedure contains an inherent limitation. Specifically, TD-FALCON selects an action by weighting the consequence of performing each and every possible action in a given state. Besides that the action selection process is inefficient with a large number of actions, the numerating step also assumes a finite set of actions, rendering it inapplicable to continuous action space. In view of this deficiency, this paper presents a direct code access procedure by which TD-FALCON can perform instantaneous searches for cognitive nodes that match with the current states and at the same time provide the highest reward values. Besides that the algorithm is much more natural and efficient, TD-FALCON can now operate with both continuous state and action spaces. Our comparative experiments based on a minefield navigation task show that TD-FALCON with direct code access produces comparable performance with the original TD-FALCON system while improving vastly in terms of computation efficiency as well as network complexity.

The rest of the paper is organized as follows. For completeness, section 2 presents a summary of the FALCON architecture and the associated learning and prediction algorithms. Section 3 presents the new TD-FALCON algorithm with the direct code access procedure. Section 4 introduces the minefield navigation simulation task and presents the experimental results. The final section concludes and provides a brief discussion of future work.

2 FALCONDynamics

FALCON employs a 3-channel architecture (Figure 1), comprising a cognitive field F c 2 and three input fields, namely a sensory field F c1 1 for representing current states, an action field F c2 1 for representing actions, and a reward field F c3 1 for representing reinforcement values. The generic network dynamics of FALCON, based on fuzzy ART operations [Carpenter et al., 1991], is described below.

Input vectors: Let S = (s1, s2, . . . , sn) denote the state vector, where si ∈ [0, 1] indicates the sensory input i. Let A =

(a1, a2, . . . , am) denote the action vector, where ai ∈ [0, 1] indicates a possible action i. Let R = (r, ¯ r) denote the reward vector, where r ∈ [0, 1] is the reward signal value and ¯ r (the complement of r) is given by ¯ r = 1 - r. Complement coding serves to normalize the magnitude of the input vectors and has been found effective in ART systems in preventing the code proliferation problem. As all input values of FALCON are assumed to be bounded between 0 and 1, normalization is necessary if the original values are not in the range of [0, 1].

Activity vectors: Let xck denote the F ck 1 activity vector for k = 1, . . . , 3. Let yc denote the F c 2 activity vector.

Weight vectors: Let wck j denote the weight vector associated with the jth node in F c 2 for learning the input patterns in F ck 1 for k = 1, . . . , 3. Initially, F c 2 contains only one uncommitted node and its weight vectors contain all 1's. When an uncommitted node is selected to learn an association, it becomes committed.

Parameters: The FALCON's dynamics is determined by choice parameters αck > 0 for k = 1, . . . , 3; learning rate parameters βck ∈ [0, 1] for k = 1, . . . , 3; contribution parameters γ ck ∈ [0, 1] for k = 1, . . . , 3 where ∑3k=1 γ ck = 1; and vigilance parameters ρck ∈ [0, 1] for k = 1, . . . , 3.

Code activation: A bottom-up propagation process first takes place in which the activities (known as choice function values) of the cognitive nodes in the F c 2 field are computed. Specifically, given the activity vectors xc1 , xc2 and xc3 (in the input fields F c1 1 , F cs 1 and F c3 1 respectively), for each F c 2 node j, the choice function T c j is computed as follows:

where the fuzzy AND operation ∧ is defined by (p ∧ q)i ≡ min(pi, qi), and the norm |.| is defined by |p| ≡ ∑i pi for vectors p and q. In essence, the choice function Tj computes the similarity of the activity vectors with their respective weight vectors of the F c 2 node j with respect to the norm of individual weight vectors.

Code competition: A code competition process follows under which the F c 2 node with the highest choice function value is identified. The winner is indexed at J where

When a category choice is made at node J, ycJ = 1; and yc

j = 0 for all j ̸= J. This indicates a winner-take-all strategy. Template matching: Before code J can be used for learning, a template matching process checks that the weight templates of code J are sufficiently close to their respective activity patterns. Specifically, resonance occurs if for each channel k, the match function mck J of the chosen code J meets its vigilance criterion:

The match function computes the similarity of the activity and weight vectors with respect to the norm of the activity vectors. Together, the choice and match functions work cooperatively to achieve stable coding and maximize code compression.

When resonance occurs, learning ensues, as defined below. If any of the vigilance constraints is violated, mismatch reset occurs in which the value of the choice function T c J is set to 0 for the duration of the input presentation. With a match tracking process, at the beginning of each input presentation, the vigilance parameter ρc1 equals a baseline vigilance ¯ ρc1. If a mismatch reset occurs, ρc1 is increased until it is slightly larger than the match function mc1 J . The search process then selects another F c 2 node J under the revised vigilance criterion until a resonance is achieved. This search and test process is guaranteed to end as FALCON will either find a committed node that satisfies the vigilance criterion or activate an uncommitted node which would definitely satisfy the criterion due to its initial weight values of 1s.

Template learning: Once a node J is selected, for each channel k, the weight vector wck J is modified by the following learning rule:

The learning rule adjusts the weight values towards the fuzzy AND of their original values and the respective weight values. The rationale is to learn by encoding the common attribute values of the input vectors and the weight vectors. For an uncommitted node J, the learning rates βck are typically set to 1. For committed nodes, βck can remain as 1 for fast learning or below 1 for slow learning in a noisy environment. When an uncommitted node is selecting for learning, it becomes committed and a new uncommitted node is added to the F c 2 field. FALCON thus expands its network architecture dynamically in response to the input patterns.

3 TD-FALCON

TD-FALCON incorporates Temporal Difference (TD) methods to estimate and learn value functions of action-state pairs Q(s, a) that indicates the goodness for a learning system to take a certain action a in a given state s. Such value functions are then used in the action selection mechanism, also known as the policy, to select an action with the maximal payoff. The original TD-FALCON algorithm proposed by Tan and Xiao (2005) selects an action with the maximal Q-value in a state s by enumerating and evaluating each available action a by presenting the corresponding state and action vectors S and A to FALCON. The TD-FALCON presented in this paper replaces the action enumeration step with a direct code access procedure, as shown in Table 1. Given the current state s, TD-FALCON first decides between exploration and exploitation by following an action selection policy. For exploration, a random action is picked. For exploitation, TD-FALCON searches for optimal action through a direct code access procedure. Upon receiving a feedback from the environment after performing the action, a TD formula is used to compute a new estimate of the Q value of performing the chosen action in the current state. The new Q value is then used as the teaching signal for TD-FALCON to learn the association of the current state and the chosen action to the estimated Q value. The details of the action selection policy, the direct code access procedure, and the Temporal Difference equation are elaborated below.

3.1 Action Selection Policy

The simplest action selection policy is to pick the action with the highest value predicted by the TD-FALCON network. However, a key requirement of autonomous agents is to explore the environment. This is especially important for an agent to function in situations without immediate evaluative feedback. If an agent keeps selecting the optimal action that it believes, it will not be able to explore and discover better alternative actions. There is thus a fundamental tradeoff between exploitation, i.e., sticking to the best actions believed, and exploration, i.e., trying out other seemingly inferior and less familiar actions.

The ϵ-greedy policy selects the action with the highest value with a probability of 1 - ϵ and takes a random action with probability ϵ [P´erez-Uribe, 2002]. With a constant ϵ value, the agent will always explore the environment with a fixed level of randomness. In practice, it may be beneficial to have a higher ϵ value to encourage the exploration of paths in the initial stage and a lower ϵ value to optimize the performance by exploiting familiar paths in the later stage. A decay ϵ-greedy policy is thus adopted to gradually reduce the value of ϵ over time. The rate of decay is typically inversely proportional to the complexity of the environment as a more complex environment with larger state and action spaces will take a longer time to explore.

3.2 Direct Code Access

In an exploiting mode, an agent, to the best of its knowledge, selects an action with the maximal reward value given the current situation (state). Through a direct code access procedure, TD-FALCON searches for the cognitive node which matches with the current state and has the maximal reward value. For direct code access, the activity vectors xc1 , xc2 , and xc3 are initialized by xc1 = S, xc2 = (1, . . . , 1), and xc3 = (1, 0). TD-FALCON then performs code activation and code competition according to equations (1) and (2) to select a cognitive node. The following lemma shows that if there is at least one cognitive node(s) encoding the current state, TD-FALCON with the given activity vectors will enable the selection of the cognitive node with the maximum reward value.

Direct Access Principle: During direct code access, given the activity vectors xc1 = S, xc2 = (1, . . . , 1), and xc3 = (1, 0), the TD-FALCON code activation and competition process will select the cognitive node J with the weight vectors wc1 J closest to S and wc3 J representing the maximal reward value, if one exists.

Proof (by Contradiction): Suppose TD-FALCON selects a F c 2 node J and there exists another F c 2 node K of which the weight vector wc1 K is more similar to S than wc1 J and the weight vector wc3 K encodes a higher reward value than wc3 J . As wc1 K is more similar to S than wc1 J , we derive that

Likewise, as wc3 K encodes a higher reward than wc3 J , we have

1. Initialize the TD-FALCON network.
2. Sense the environment and formulate a state representation s.
3. Following an action selection policy, first make a choice between exploration and exploitation. If exploring, take a random action. If exploiting, identify the action a with the maximal Q(s,a) value by presenting the state vector S, the action vector A=(1,...1), and the reward vector R=(1,0) to TD-FALCON.
4. Perform the action a, observe the next state s′ , and receive a reward r (if any) from the environment.
5. Estimate the revised value functionQ(s, a) following a Temporal Difference formula such as ΔQ(s, a) = αTDerr.
6. Present the corresponding state, action, and reward (Q-value) vectors (S, A, and R) to TD-FALCON for learning.
7. Update the current state by s=s'.
8. Repeat from Step 2 until s is a terminal state.

By equation (1), the above conditions imply that T cK > T c J , which means node K should be selected by TD-FALCON instead of node J (Contradiction).

[End of Proof]

Upon selecting a winning F c 2 node J, the chosen node J performs a readout of its weight vector to the action field F c2 1 such that

An action aI is then chosen, which has the highest activation value

3.3 Learning Value Function

A typical Temporal Difference equation for iterative estimation of value functions Q(s,a) is given by

where α ∈ [0, 1] is the learning parameter and TDerr is a function of the current Q-value predicted by TD-FALCON and the Q-value newly computed by the TD formula.

TD-FALCON employs a Bounded Q-learning rule, wherein the temporal error term is computed by

where TDerr = r + γmaxa′Q(s′ , a′ ) - Q(s, a), of which r is the immediate reward value, γ ∈ [0, 1] is the discount parameter, and maxa′Q(s′ , a′ ) denotes the maximum estimated value of the next state s′ . It is important to note that the Q values involved in estimating maxa′Q(s′ , a′ ) are computed by the same FALCON network itself and not by a separate reinforcement learning system. The Q-learning update rule is applied to all states that the agent traverses. With value iteration, the value function Q(s, a) is expected to converge to r + γmaxa′Q(s′ , a′ ) over time. By incorporating the scaling term 1 - Q(s, a), the adjustment of Q values will be self-scaling so that they will not be increased beyond 1. The learning rule thus provides a smooth normalization of the Q values. If the reward value r is constrained between 0 and 1, we can guarantee that the Q values will remain to be bounded between 0 and 1.

4 The Minefield Navigation Task

The objective of the given task is to teach an autonomous vehicle (AV) to navigate through a minefield to a randomly selected target position in a specified time frame without hitting a mine. In each trial, the AV starts from a randomly chosen position in the field, and repeats the cycles of sense, act, and learn. A trial ends when the AV reaches the target (success), hits a mine (failure), or exceeds 30 sense-act-learn cycles (out of time). The target and the mines remain stationary during the trial. All results reported in this paper are based on a 16 by 16 minefield containing 10 mines as illustrated in Figure 2.

The AV has a rather coarse sensory capability with a 180 degree forward view based on five sonar sensors. For each direction i, the sonar signal is measured by si = 1 di , where di is the distance to an obstacle (that can be a mine or the boundary of the minefield) in the i direction. Other input attributes of the sensory (state) vector include the bearing of the target from the current position. In each step, the AV can choose one out of the five possible actions, namely move left, move diagonally left, move straight ahead, move diagonally right, and move right. At the end of a trial, a reward of 1 is given when the AV reaches the target. A reward of 0 is given when the AV hits a mine. For the delayed reward scheme, no immediate reward is given at each step of the trial. A reward of 0 is given when the system runs out of time.

For learning the minefield task, we use a TD-FALCON network containing 18 nodes in the sensory field (representing 5x2 complement-coded sonar signals and 8 target bearing values), 5 nodes in the action field, and 2 nodes in the reward field (representing the complement-coded function value). TD-FALCON with direct code access employed a set of parameter values obtained through empirical experiments: choice parameters αc1 = 0.1, αc2 = 0.001, αc3 = 0.001; learning rate βck = 1.0 for k = 1, 2, 3 for fast learning; contribution parameters γ c1 = γ c2 = γ c3 = 13 ; baseline vigilance parameters ¯ ρc1 = 0.25 and ¯ ρc2 = 0.2 for a marginal level of match requirement in the state and action spaces, and ¯ ρc3 = 0.5 for a stricter match criterion on reward values. For Temporal Difference learning, the learning rate α was fixed at 0.5 and the discount factor γ was set to 0.9. The initial Q value was set to 0.5. For action selection policy, ϵ was initialized to 0.5 and decayed at a rate of 0.0005 until it dropped to 0.005.

To put the performance of FALCON in perspective, we further conducted experiments to evaluate the performance of an alternative reinforcement learning system, using the standard Q-learning rule and a multi-layer perceptron network, trained with a gradient descent based backpropagation algorithm, as the function approximator. We have chosen the backpropagation (BP) algorithm as the reference for comparison as gradient descent is by far one of the most widely used universal function approximation techniques and has been applied in many contexts, including Q-learning [Sun et al., 2001] and adaptive critic [Werbos, 2004]. The BP learner employed a standard three-layer feedforward architecture to learn the value function with a learning rate of 0.25 and a momentum term of 0.5. The input layer consisted of 18 nodes representing the 5 sonar signal values, 8 possible target bearings, and 5 selectable actions. The output layer consisted of only one node representing the value of performing an action in a particular state. A key issue in using a BP network is the determination of the number of hidden nodes. We experimented with a varying number of nodes empirically and obtained the best results with 36 nodes. To enable a fair comparison, the BP learner also made use of the same action selection module based on the decay ϵ-greedy policy.

Figure 3 summarizes the performance of TD-FALCON with direct code access (FALCON-DA), the original TDFALCON with action enumeration (FALCON-AE), and the BP reinforcement learner in terms of success rates averaged at 200-trial intervals over 3000 trials across 10 sets of experiments. We observed that the success rates of both FALCONDA and FALCON-AE increased steadily right from the beginning. Beyond 1000 trials, both systems can achieve over 90 percent success rates. The backpropagation (BP) based reinforcement learner on the other hand required a much longer exploration phase. In fact, the BP learner only managed to reach around 90% success rates at 50,000 trials with a lower ϵ decay rate of 0.00001. Therefore, in the first 3000 trials, its success rates remained under 10%.

To evaluate how well the AV traverses from its starting position to the target, we define a measure called normalized step given by stepn = step sd , where step is the number of sense-move-learn cycles taken to reach the target and sd is the shortest distance between the starting and target positions. A normalized step of 1 means the system has taken the optimal (shortest) path to the target. As depicted in Figure 4, after 1000 trials, both FALCON-AE and FALCON-DA were able to reach the target in optimal or close to optimal paths in a great majority of the cases. The BP learner as expected produced unsatisfactory performance in terms of path optimality.

Considering network complexity, FALCON-DA demonstrated a great improvement over FALCON-AE by creating a much smaller set of cognitive nodes. In fact, the FALCONDA networks consisting of around 38 cognitive nodes were almost the same size as a BP network with 36 hidden nodes. With a much more compact network structure, the efficiency of FALCON-DA in terms of computation time was also much better than FALCON-AE. The average reaction time taken to complete a sense-act-learn cycle clocked 0.12 millisecond, in contrast to 4 to 5 milliseconds as required by FALCON-AE.

5 Conclusion

We have presented an enhanced TD-FALCON model with a direct code access mechanism for selecting optimal actions in reinforcement learning. Besides that the network dynamics is more direct and natural, our comparative experiments show that TD-FALCON with direct code access is much more efficient than its predecessor in terms of computation time as well as network complexity. With a highly efficient learning architecture, our future work will involve applying FALCON to more complex and challenging domains. Another interesting extension is to interpret the learned cognitive nodes for explanation of the system's behaviour in performing specific tasks.