Production-based Cognitive Models as a Test Suite for Reinforcement Learning Algorithms (2020)

Abstract: We introduce a framework in which production-rule based computational cognitive modeling and Reinforcement Learning can systematically interact and inform each other. We focus on linguistic applications because the sophisticated rule-based cognitive models needed to capture linguistic behavioral data promise to provide a stringent test suite for RL algorithms, connecting RL algorithms to both accuracy and reaction-time experimental data. Thus, we open a path towards assembling an experimentally rigorous and cognitively realistic benchmark for RL algorithms. We extend our previous work on lexical decision tasks and tabular RL algorithms (Brasoveanu and Dotlačil, 2020b) with a discussion of neural-network based approaches, and a discussion of how parsing can be formalized as an RL problem.

## reinforcement learning and production-based cognitive models we introduce a framework in which we can start exploring how reinforcement learning (rl; sutton and barto 2018) algorithms scale up against human cognitive performance, as captured by complex, production-based cognitive models. our ultimate goal is to focus on sophisticated cognitive models of linguistic skills, e.g., the parsers in @xcite ; @xcite ; @xcite , because cognitive models that use theoreticallygrounded linguistic representations and processes call for richly structured representations and complex rule systems that pose significant challenges for rl algorithms. these cognitive models, which capture humanparticipant accuracy and latency data obtained from forced-choice and reaction-time experiments, can provide exacting, experimentally established benchmarks for the performance of artificial rl agents. these benchmarks will enable us to see if and when different rl algorithms fail, and how exactly they fail. in this paper, we report a small pilot study that exemplifies three modes of failure. neural-network based function-approximation approaches sometimes (i) fail to learn even fairly simple rule systems in a stable manner. even when they seem to learn, (ii) they fail by learning a lot of noise (incorrect rules), particularly in more complex tasks. tabular approaches fare better, but (iii) learn complex tasks much more slowly, and still learn a lot of noise in more complex tasks, albeit less so than neural-network approaches. bridging the rl-cognitive modeling divide also promises to shed new light on the issue of cognitive model learnability. the learnability problem for production-rule based models can be divided into two parts: (i) rule acquisition -forming complex rules out of simpler ones, and (ii) rule orderingdeciding which rule to fire when. we focus here on the easier problem of rule ordering, and show how, on one hand, linguistic cognitive models provide a benchmark for rl algorithms and, on the other hand, rl provides a framework to systematically investigate cognitive model learnability in a formally and computationally explicit way. we investigate the issue of rule-ordering learning using the adaptive control of thought-rational (act-r) cognitive architecture (see @xcite . the advantage of using act-r is that this cognitive architecture and rl have very close, albeit largely unexplored, connections @xcite @xcite . act-r tries to address the rule acquisition and ordering problems, but its proposed solutions -production compilation and rule-utility estimation, respectively -have not been systematically applied to complex models for linguistic skills (apart from @xcite investigates the role of production compilation in morphology acquisition). after a brief overview of act-r and the description of a linguistic task for which rule-ordering learning will be studied (section 2), we show how the linguistic task can be analyzed as an rl problem (section 3), and discuss the results of our experiments with tabular and neural-network based q-learning algorithms (section 4). we then briefly discuss how parsing can be formalized as an rl problem (section 5), and conclude with a summary and some directions for future work (section 6). ## learning goal-conditioned rules in lexical decision: a simple test case there are two types of memory in act-r. on one hand, we have declarative memory ('knowing that'), which encodes our knowledge of facts. facts are represented as chunks / attribute-value matrices, e.g., the lexical chunk for the word elephant: isa: word form: elephant meaning: elephant category: noun number: an example production is provided in (2): if the current cognitive state is such that the goal buffer (which drives cognitive processes in act-r) encodes a task of 'retrieving' the lexical entry for the form 'elephant,' then (=⇒), we take the action of placing a retrieval (buffer) request to search declarative memory for a word with the form 'elephant,' and we consequently update the task in the goal buffer to one of 'retrieval done.' the act-r architecture constrains cognitive behavior in various ways, two of which are that (i) buffers can hold only one chunk, and (ii) only one production can fire at any given time. the framework and the range of issues that emerge when we try to systematically bridge rl and act-r are best showcased with a simple kind of linguistic tasks: lexical decision (ld) tasks. we briefly outline in section 5 how to extend this approach to parsing models implemented in act-r. in an ld task, human participants see a string of letters on a screen. if the participants think the string of letters is a word, they press one key (j in our setup). if they think the string is not a word, they press a different key (f in our setup). after pressing the key, the next stimulus is presented. we will investigate the extent to which two kinds of rl agents can be used to learn goal-conditioned rules in an act-r based cognitive model of ld tasks. the main point of proposing and examining an act-r model of ld tasks is to construct a simple example of a production-rule based model that enables us to study learnability issues associated with rl algorithms. our discussion recapitulates the main results in @xcite , and extends them with an initial foray into neuralnetwork based rl approaches. the ld model and rl algorithms can be scaled up in future work to more complex and cognitively realistic syntactic and semantic parsing models, since ld is basically a subcomponent of parsing. the ld model provides the basic scaffolding of production rules needed for ld tasks, which is all that we need for our purposes: fleshing it out to capture major experimental results about ld, or comparing it to previously proposed cognitive models of ld is not our focus here. we model three ld tasks of increasing length, hence difficulty: (i) a 1-stimulus task consisting only of the word elephant, (ii) a 2-stimuli task consisting of the word elephant and a non-word, and (iii) a 4-stimuli task consisting of the word elephant, a non-word, the word dog, and another non-word. the model components are split between declarative memory, which stores the lexical knowledge of an english speaker, and procedural memory, which stores rules that enable the model to carry out the ld task. ld tasks can be modeled in act-r with a small number of rules (see @xcite ). we will assume 4 rules, provided in standard act-r format below. these rules were originally hand-coded to fire serially by conditioning all the actions on specific goal states. the goal conditions are stricken out, indicating that goal states were not provided to the rl agents: the order of the rules was not hand-coded for them. instead, we want the rl agents to learn the rule ordering. rule 1: retrieving @xmath0: retrieving @xmath1: =val value: ∼@xmath2: retrieval done +@xmath3: word form: =val rule 2: lexeme retrieved @xmath4: retrieval done @xmath5: full state: @xmath6: retrieving +@xmath7: press-key key: j rule 3: no lexeme found @xmath8: retrieval done @xmath9: empty state: @xmath10: retrieving +@xmath11: press-key key: f rule 4: finished @xmath12: retrieving @xmath13: @xmath14: done with fully specified, hand-coded rules, the ld task unfolds as follows. assume the initial goal state of the act-r model is retrieving, and the word elephant appears on the virtual screen of the model, which is automatically stored in the value slot of the visual buffer. at this initial stage, the preconditions of rule 1 are satisfied, so the rule fires. this starts an attempt to retrieve a word with the form elephant from declarative memory, and the goal state is updated to retrieval done. when the word is successfully retrieved, rule 2 fires and the j key is pressed. at that point: i. in the 1-stimulus task, the text finished is displayed, then rule 4 fires and ends the task; thus, the rule sequences for the 3 ld tasks are as shown in (3), assuming fully specified, handcoded rules. however, as we mentioned, we do not hand-code the goal-state preconditions, indicated by striking out the goal states in the 4 rules above. we only specify the actions (and preconditions associated with buffers other than the goal buffer) and let the rl agents, which can select any rule at any given time, learn to carry out the ld tasks. we see that proper rule ordering / sequencing is crucial to successfully completing an ld task, which is like searching for a path through a maze: ## rule ordering as an rl problem markov decision processes (mdps) are the stochastic models of sequential decision-making that form the basis of rl approaches to learning. in an mdp, an agent interacts with its environment and needs to make decisions at discrete time steps @xmath15, 2, . . . , n. defining what counts as the agent and what counts as its environment is part of the modeling process. at every step t, all the information from the past relevant for the current action selection is captured in the current state of the process s t . this is the markov property: the future is independent of the past given the current state. as figure 1 shows, the environment passes to the agent a state s t and, at the same time, a reward signal r t . the agent observes the current state s t and reward r t and takes an action a t , which is passed from the agent to the environment. the cycle then continues: at time step t + 1, the environment responds to the agent's action with a new state s t+1 and a new reward signal r t+1 . based on these, the agent selects a new action a t+1 etc. the definitions of 'state' and 'action' depend on the problem, and are part of the modeling process, just like defining what counts as the agent and its environment. the agent's policy is a complete specification of what action to take at any time step. given the markovian nature of the mpd, the policy π is effectively a mapping from the state space s to the action space a, π : @xmath16. a deterministic policy is a mapping from any given state s t to an action a @xmath17, while a stochastic policy is a mapping from any given state s t to a probability distribution over actions a t ∼ π(s t ). the agent's goal is to maximize some form of cumulative reward over an episode, which is a com-plete, usually multi-step interaction between the agent and its environment. in our case, an episode would be a full simulation of a 1/2/4-stim ld task. the agent learns (solves/optimizes the mdp) by updating its policy π to maximize the (per-episode) cumulative reward. the standard cumulative reward for an episodic task is the discounted return g: at time step @xmath18, g @xmath19, i.e., g t is the sum of the current reward and the discounted future rewards until the final step n of the episode. future rewards are discounted in finite / episodic tasks because the agent has a preference for more immediate rewards. the present value of future rewards is determined by the discount factor γ (0 ≤ γ ≤ 1). we define the (state-)action value function q π (s, a) to be the expected (discounted) return when starting in state s, performing action a and then following the policy π until the end of the episode. the agent selects actions with the goal of maximizing its expected discounted return. if we estimate the q function for a given policy based on the interactions between the agent and its environment, i.e., based on experience, we can improve that policy by 'greedification:' given a state s, we can always select the optimal action in s, i.e., the action with the maximal expected return according to our current q estimate. q-learning algorithms, which are the focus of our investigation here (given their widespread use), come in various flavors. the simplest one is tabular q-learning @xcite , which is fairly effective for our ld tasks. we will also investigate approaches that approximate the q-function with neural networks, specifically deep q-networks @xcite . in tabular q-learning, the q function s×@xmath20. the q table is initialized to an arbitrary fixed value (0). the agent then updates the q table incrementally at each time step t: the value of the pair (s t , a t ), where s t is the state relative to which the agent took action a t , is updated based on the reward signal r t+1 and the new state s t+1 that the agent receives back from the environment after taking action a t . q-learning is a form of temporal difference (td) learning, as shown in (4). the q new value estimate for the state-action pair (s t , a t ) is based on the q old value, updated by some proportion α (the learning rate; 0 < α ≤ 1) of the td error. the td error is the difference between the td target -which is an updated estimate of the value of the (s t , a t ) pair -and the q old value estimate. the td target consists of (i) the reward r t+1 the agent receives after action a t , which is part of the new data the agent gets back from the environment after action a t , plus (ii) the estimate of the value of the next state s t+1 , where the next state s t+1 is the other part of the new data the agent gets back from the environment after action a t . the q-learning optimal estimate for the value of the next state s t+1 is discounted by γ, since this state is in the future relative to the state-action pair (s t , a t ) we're currently updating. this optimal estimate for s t+1 is aggressively confident / optimistic (in contrast to expected sarsa, for example; see @xcite ): the agent looks at all the possible actions a t+1 that can be taken in state s t+1 and assumes that the action a t+1 with the highest q old -value provides an accurate estimate of the s t+1 value. for tabular q-learning, the agent (in the rl sense) is a q-value table that assigns values to all possible state-action pairs and that guides the rule selection process at every cognitive step. the environment is the cognitive state of the act-r model / mind, which could conceivably consist of (i) all the modules (procedural memory, declarative memory and visual and motor modules) together with (ii) their associated buffers @xcite where and the manual buffer). this, however, would lead to a very large state space s, which in turn would lead to a large q-value table. dqn and similar neural-network approaches can help with the large state-space problem, but we will nonetheless take a state s to consist just of: (i) the goal buffer, (ii) the retrieval buffer, (iii) the value in the visual-what buffer, if any, and finally, (iv) the state of the manual buffer (busy or free). for example, the state after the word elephant is retrieved from declarative memory is: goal: {state: retrieval done}, retrieval: {form: elephant}, visual value: elephant, manual: free. the action space consists of the 4 rules above, namely retrieving, lexeme retrieved, no lexeme found and finished, together with a special action none that the agent selects when it wants to not fire any rule because it prefers to wait for a new cognitive state. the reward structure is as follows: (i) the agent receives a positive reward of 1 at the end of an episode (when the ld task is completed), specifically, when the goal state is done; (ii) the agent receives a negative reward of -0.15 for every rule it selects, other than none; (iii) there is no penalty for waiting and selecting no rule, i.e., for selecting the special action none, which is optimal when waiting for retrieval requests from declarative memory to complete, for example; (iv) finally, at every step, the agent receives a negative reward equal to the amount of time that has elapsed between the immediately preceding step and the current step (multiplied by -1 to make it negative). this reward structure is designed to encourage the agent to finish the task as soon as possible by selecting the smallest number of rules. the negative temporal reward (iv) discourages the agent from just repeatedly selecting an action, e.g., none. this ends up timing out the ld task in a small number of steps and fast-forwards the agent to the maximum waiting time per stimulus the act-r environment allows for, which we set to 2 seconds per word for the ld task. thus, given a simple reward structure that incorporates fairly minimal cognitive assumptions, rl enables us to induce proper rule sequences to complete the ld tasks: rl enables us to leverage the simple assumptions built into the reward structure to solve the much harder rule-ordering problem by direct experience / trial-and-error interaction with the ld tasks. ## experiments and results we assume the usual act-r defaults, e.g., rule firing time is set to 50 ms. the discount factor γ is set to 0.95 and the learning rate α is set to 10 -3 . we use an -greedy policy to balance exploration and exploitation, with annealed from a maximum of 1 to a minimum of 0.01. we investigate two types of agents / algorithms: (i) tabular q-learning (the main results for tabular agents are from @xcite , and (ii) dqn. to a large extent, the agents learn by trial and error to successfully carry out the ld tasks: they learn how to properly order the rules figure 3: dqn: steps per episode for 1-stim (left), 2-stim (middle) and 4-stim (right) tasks and complete the ld tasks as efficiently as possible. this is no small feat given that the actual number of steps, i.e., decision points, when the agents needs to select an action, is larger than the high-level sequences of rule firings in (3) above. for example, for a 1-stim task, there are actually 12 steps where the agent needs to decide whether to wait or to fire a specific rule (when the agent does not complete the task perfectly, it might take much more than 12 steps). the 2-stim task requires 18 such steps (if perfectly completed), and the 4-stim task requires 34 steps (again, if perfectly completed). the reason for the higher number of steps compared to the number of rules is that our ld simulations involve the visual and motor modules (to read strings of characters and to press keys) in addition to the declarative memory module. visual and motor actions, just as retrievals from declarative memory, take time, and the agent needs to make decisions while waiting for them to complete. ## parsing as an rl problem in this section, we briefly discuss how parsing can be formalized as an rl problem. just as the ld task, the parsing task can be implemented in act-r (cf. @xcite @xcite . the parser components are split over various act-r modules and buffers: (i) lexical knowledge is encoded in declarative memory, (ii) knowledge of grammar and parsing actions are encoded in procedural memory, (iii) expectations about upcoming syntactic categories are encoded in the goal buffer, (iv) information about the current partially-built syntactic parse is encoded in the imaginal buffer (a secondary goal-like buffer), and finally, (v) visual information from the environment is transferred via the visual buffer. we consider a simple example, which features an eager left-corner parser @xcite . assume we have a simple grammar with four phrase structure rules: (i) @xmath21, (ii) @xmath22, (iii) @xmath23, (iv) @xmath24. also, assume that we are reading the sentence a boy sleeps word by word. as shown in figure 4 , we start with the empty visual buffer and our goal stack (the stack of the expected syntactic categories) consists of just s: our goal is to parse a sentence. we then shift focus to the first word, the information is transferred to the goal buffer, at which point we retrieve its syntactic category det(erminer) from declarative memory. we can now take a series