{'fraction_non_alphanumeric': 0.03903596979987472, 'fraction_numerical': 0.012165770993373116, 'mean_word_length': 4.535036496350365, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards a learning-theoretic analysis of spike-timing dependent plasticity

This paper suggests a learning-theoretic perspective on how synaptic plasticity benefits global brain functioning. We introduce a model, the selectron, that (i) arises as the fast time constant limit of leaky integrate-and-fire neurons equipped with spiking timing dependent plasticity (STDP) and (ii) is amenable to theoretical analysis. We show that the selectron encodes reward estimates into spikes and that an error bound on spikes is controlled by a spiking margin and the sum of synaptic weights. Moreover, the efficacy of spikes (their usefulness to other reward maximizing selectrons) also depends on total synaptic strength. Finally, based on our analysis, we propose a regularized version of STDP, and show the regularization improves the robustness of neuronal learning when faced with multiple stimuli.


Introduction
Finding principles underlying learning in neural networks is an important problem for both artificial and biological networks. An elegant suggestion is that global objective functions may be optimized during learning [1]. For biological networks however, the currently known neural plasticity mechanisms use a very restricted set of data -largely consisting of spikes and diffuse neuromodulatory signals. How a global optimization procedure could be implemented at the neuronal (cellular) level is thus a difficult problem.
A successful approach to this question has been Rosenblatt's perceptron [2] and its extension to multilayer perceptrons via backpropagation [3]. Similarly, (restricted) Boltzmann machines, constructed from simple stochastic units, have provided a remarkably powerful approach to organizing distributed optimization across many layers [4]. By contrast, although there has been significant progress in developing and understanding more biologically realistic models of neuronal learning [5][6][7][8][9][10], these do not match the performance of simpler, more analytically and computationally tractable models in learning tasks.
Overview. This paper constructs a bridge from biologically realistic to analytically tractable models. The selectron is a model derived from leaky integrate and fire neurons equipped with spiketiming dependent plasticity that is amenable to learning-theoretic analysis. Our aim is to extract some of the principles implicit in STDP by thoroughly investigating a limit case.
Section §2 introduces the selectron. We state a constrained reward maximization problem which implies that selectrons encode empirical reward estimates into spikes. Our first result, section §3, is that the selectron arises as the fast time constant limit of well-established models of neuronal spiking and plasticity, suggesting that cortical neurons may also be encoding reward estimates into their spiketrains.
Two important questions immediately arise. First, what guarantees can be provided on spikes being reliable predictors of global (neuromodulatory) outcomes? Second, what guarantees can be provided on the usefulness of spikes to other neurons? Sections §4 and §5 answer these questions by providing an upper bound on a suitably defined 0/1 loss and a lower bound on the efficacy of a selectron's spikes, measured in terms of its contribution to the expected reward of a downstream selectron. Both bounds are controlled by the sum of synaptic weights w 1 , thereby justifying the constraint introduced in §2. Finally, motivated by our analysis, §6 introduces a regularized STDP rule and shows that it learns more robustly than classical STDP. §7 concludes the paper. Proofs of theorems are provided in the supplementary material.
Related work. Spike-timing dependent plasticity and its implications for the neural code have been intensively studied in recent years. The work closest in spirit to our own is Seung's "hedonistic" synapses, which seek to increase average reward [6]. Our work provides guarantees on the finite sample behavior of a discrete-time analog of hedonistic neurons. Another related line of research derives from the information bottleneck method [9,11] which provides an alternate constraint to the one considered here. An information-theoretic perspective on synaptic homeostasis and metabolic cost, complementing the results in this paper, can be found in [12,13]. Simulations combining synaptic renormalization with burst-STDP can be found in [14].
Important aspects of plasticity that we have not considered here are properties specific to continuoustime models, such as STDP's behavior as a temporal filter [15], and also issues related to convergence [8,10].
The learning-theoretic properties of neural networks have been intensively studied, mostly focusing on perceptrons, see for example [16]. A non-biologically motivated "large-margin" analog of the perceptron was proposed in [17].

The selectron
We introduce the selectron, which can be considered a biologically motivated adaptation of the perceptron, see §3. The mechanism governing whether or not the selectron spikes is a Heaviside function acting on a weighted sum of synaptic inputs; our contribution is to propose a new reward function and corresponding learning rule. Let us establish some notation. Let X denote the set of N -dimensional {0, 1}-valued vectors forming synaptic inputs to a selectron, and Y = {0, 1} the set of outputs. A selectron spikes according to is the Heaviside function and w is a [0, 1] ⊂ R valued N -vector specifying the selectron's synaptic weights. Let P (x) denote the probability of input x arising.
To model the neuromodulatory system we introduce random variable ν : X → {−1, 0, +1}, where positive values correspond to desirable outcomes, negative to undesirable and zero to neutral. Let P (ν|x) denote the probability of the release of neuromodulatory signal subsequent to input x.
The reward consists in three components. The first term is the neuromodulatory signal, which acts as a supervisor. The second term is the total current w x minus the threshold ϑ. It is analogous to the margin in support vector machines or boosting algorithms, see section §4 for a precise formulation.
The third term gates rewards according to whether or not the selectron spikes. The reward is thus selected 1 : neuromodulatory signals are ignored by the selectron's reward function when it does not spike, enabling specialization.
Constrained reward maximization. The selectron solves the following optimization problem: maximize: subject to: w 1 ≤ ω for some ω > 0.
Remark 1 (spikes encode rewards). Optimization problem (3) ensures that selectrons spike for inputs that, on the basis of their empirical sample, reliably lead to neuromodulatory rewards. Thus, spikes encode expectations about rewards.
The constraint is motivated by the discussion after Theorem 1 and the analysis in §4 and §5. We postpone discussion of how to impose the constraint to §6, and focus on reward maximization here.
The reward maximization problem cannot be solved analytically in general. However, it is possible to use an iterative approach. Although f w (x) is not continuous, the reward function is a continuous function of w and is differentiable everywhere except for the "corner" where w x − ϑ = 0. We therefore apply gradient ascent by computing the derivative of (3) with respect to synaptic weights to obtain online learning rule where update factor α controls the learning rate.
The learning rule is selective: regardless of the neuromodulatory signal, synapse w jk is updated only if there is both an input x j = 1 and output spike y = f w (x) = 1.
The selectron is not guaranteed to find a global optimum. It is prone to initial condition dependent local optima because rewards depend on output spikes in learning rule (4). Although this is an undesirable property for an isolated learner, it is less important, and perhaps even advantageous, in large populations where it encourages specialization.
Remark 2 (unsupervised setting). Define the unsupervised setting by ν(x) = 1 for all x. The reward function reduces to R(x, f w ) = (w x − ϑ) · f w (x). Without the constraint synapses will saturate. Imposing the constraint yields a more interesting solution where the selectron finds a weight vector summing to ω which balances (i) frequent spikes and (ii) high margins.
Theorem 1 (Controlling the frequency of spikes). Assuming synaptic inputs are i.i.d. Bernoulli variables with P (spike) = p, then The Bernoulli regime is the discrete-time analog of the homogeneous Poisson setting used to prove convergence of reward-modulated STDP in [8]. Interestingly, in this setting the constraint provides a lever for controlling (lower bounding) rewards per spike If inputs are not Bernoulli i.i.d., then P (y = 1) and ω still covary, although the precise relationship is more difficult to quantify. Although i.i.d. inputs are unrealistic, note that recent neurophysiological evidence suggests neuronal firing -even of nearby neurons -is uncorrelated [18].

Relation to leaky integrate-and-fire neurons equipped with STDP
The literature contains an enormous variety of neuronal models, which vary dramatically in sophistication and the extent to which they incorporate the the details of the underlying biochemical processes. Similarly, there is a large menagerie of models of synaptic plasticity [19]. We consider two well-established models: Gerstner's Spike Response Model (SRM) which generalizes leaky integrate-and-fire neurons [20] and the original spike-timing dependent plasticity learning rule proposed by Song et al [5], and show that the selectron arises in the fast time constant limit of the two models.
First let us recall the SRM. Suppose neuron n k last outputted a spike at time t k and receives input spikes at times t j from neuron n j . Neuron n k spikes or according to the Heaviside function applied to the membrane potential M w : Input and output spikes add to the membrane potential for t j ≤ t and t k ≤ t respectively. Here τ m and τ s are the membrane and synapse time constants.
The original STDP update rule [5] is where τ + and τ − are time constants. STDP potentiates input synapses that spike prior to output spikes and depotentiates input synapses that spike subsequent to output spikes. Theorem 2 (the selectron is the fast time constant limit of SRM + STDP). In the fast time constant limit, lim τ• → 0, the SRM transforms into a selectron with Moreover, STDP transforms into learning rule (4) in the unsupervised setting with ν(x) = 1 for all x. Finally, STDP arises as gradient ascent on a reward function whose limit is the unsupervised setting of reward function (2).
Theorem 2 shows that STDP implicitly maximizes a time-discounted analog of the reward function in (3). We expect many models of reward-modulated synaptic plasticity to be analytically tractable in the fast time constant limit. An important property shared by STDP and the selectron is that synaptic (de)potentiation is gated by output spikes, see §A.1 for a comparison with the perceptron which does not gate synaptic learning

An error bound
Maximizing reward function (3) implies that selectrons encode reward estimates into their spikes. Indeed, it recursively justifies incorporating spikes into the reward function via the margin (w x − ϑ), which only makes sense if upstream spikes predict reward. However, in a large system where estimates pile on top of each other there is a tendency to overfit, leading to poor generalizations [21]. It is therefore crucial to provide guarantees on the quality of spikes as estimators.
Boosting algorithms, where the outputs of many weak learners are aggregated into a classifier [22], are remarkably resistant to overfitting as the number of learners increases [23]. Cortical learning may be analogous to boosting: individual neurons have access to a tiny fraction of the total brain state, and so are weak learners; and in the fast time constant limit, neurons are essentially aggregators.
We sharpen the analogy using the selectron. As a first step towards understanding how the cortex combats overfitting, we adapt a theorem developed to explain the effectiveness of boosting [24]. The goal is to show how the margin and constraint on synaptic weights improve error bounds. Definition 2. A selectron incurs a 0/1 loss if a spike is followed by negative neuromodulatory feedback The 0/1 loss fails to take the estimates (spikes) of other selectrons into account and is difficult to optimize, so we also introduce the hinge loss: Note that l ≤ h κ for all κ ≥ 1. Parameter κ controls the saturation point, beyond which the size of the margin makes no difference to h κ .
An alternate 0/1 loss 2 penalizes a selectron if it (i) fires when it shouldn't, i.e. when ν(x) = −1 or (ii) does not fire when it should, i.e. when ν(x) = 1. However, since the cortex contains many neurons and spiking is metabolically expensive [25], we propose a conservative loss that only penalizes errors of commission ("first, do no harm") and does not penalize specialization. Theorem 3 (spike error bound).
Suppose each selectron has ≤ N synapses. For any selectron n k , let Remark 3 (theoretical justification for maximizing margin and constraining w 1 ). The theorem shows how subsets of distributed systems can avoid overfitting. First, it demonstrates the importance of maximizing the margin (i.e. the empirical reward). Second, it shows the capacity term depends on the number of synapses N and the constraint ω on synaptic weights, rather than the capacity of S k -which can be very large.
The hinge loss is difficult to optimize directly since gating with output spikes f w (x) renders it discontinuous. However, in the Bernoulli regime, Theorem 1 implies the bound in Theorem 3 can be rewritten as (8) and so ω again provides the lever required to control the 0/1 loss. The constraint w 1 ≤ ω is best imposed offline, see §6.

A bound on the efficacy of inter-neuronal communication
Even if a neuron's spikes perfectly predict positive neuromodulatory signals, the spikes only matter to the extent they affect other neurons in cortex. Spikes are produced for neurons by neurons. It is therefore crucial to provide guarantees on the usefulness of spikes.
In this section we quantify the effect of one selectron's spikes on another selectron's expected reward. We demonstrate a lower bound on efficacy and discuss its consequences.
Definition 3. The efficacy of spikes from selectron n j on selectron n k is i.e. the expected contribution of spikes from selectron n j to selectron n k 's expected reward, relative to not spiking. The notation is intended to suggest an analogy with differentiation -the infinitesimal difference made by spikes on a single synapse.
In other words, if spikes from n j make no difference to the expected reward of n k .
The following theorem relies on the assumption that the average contribution of neuromodulators is higher after n j spikes than after it does not spike (i.e. upstream spikes predict reward), see §A.6 for precise statement. When the assumption is false the synapse w jk should be pruned. Theorem 4 (spike efficacy bound). Let p j := E[Y j ] denote the frequency of spikes from neuron n j . The efficacy of n j 's spikes on n k is lower bounded by where c 2 is described in §A.6 and w C The efficacy guarantee is interpreted as follows. First, the guarantee improves as co-spiking by n j and n k increases. However, the denominators imply that increasing the frequency of n j 's spikes worsens the guarantee, insofar as n j is not correlated with n k . Similarly, from the third term, increasing n k 's spikes worsens the guarantee if they do not correlate with n j .
An immediate corollary of Theorem 4 is that Hebbian learning rules, such as STDP and the selectron learning rule (4), improve the efficacy of spikes. However, it also shows that naively increasing the frequency of spikes carries a cost. Neurons therefore face a tradeoff. In fact, in the Bernoulli regime, Theorem 1 implies (9) can be rewritten as so the constraint ω on synaptic strength can be used as a lever to improve guarantees on efficacy. Remark 4 (efficacy improved by pruning weak synapses). The 1 st term in (9) suggests that pruning weak synapses increases the efficacy of spikes, and so may aid learning in populations of selectrons or neurons.

Experiments
Cortical neurons are constantly exposed to different input patterns as organisms engage in different activities. It is therefore important that what neurons learn is robust to changing inputs [26,27]. In this section, as proof of principle, we investigate a simple tweak of classical STDP involving offline regularization. We show that it improves robustness when neurons are exposed to more than one pattern.
Observe that regularizing optimization problem (3) yields maximize: learning rule: incorporates synaptic renormalization directly into the update. However, (12) requires continuously re-evaluating the sum of synaptic weights. We therefore decouple learning into an online reward maximization phase and an offline regularization phase which resets the synaptic weights.
A similar decoupling may occur in cortex. It has recently been proposed that a function of NREM sleep may be to regulate synaptic weights [28]. Indeed, neurophysiological evidence suggests that average cortical firing rates increase during wakefulness and decrease during sleep, possibly reflecting synaptic strengths [29,30]. Experimental evidence also points to a net increase in dendritic spines (synapses) during waking and a net decrease during sleep [31].
Setup. We trained a neuron on a random input pattern for 10s to 87% accuracy with regularized STDP. See §A.7 for details on the structure of inputs. We then performed 700 trials (350 classical and 350 regularized) exposing the neuron to a new pattern for 20 seconds and observed performance under classical and regularized STDP.
Regularized STDP consists of a small tweak of classical STDP in the online phase, and an additional offline regularization phase: • Online. In the online phase, reduce the depotentiation bias from 0.85α + in the classical implementation to α − = 0.75α + . • Offline. In the offline phase, modify synapses once per second according to where s is output spikes per second, ω = 5Hz is the target rate and update factor γ = 0.6. The offline update rule is firing rate, and not spike, dependent.
Classical STDP has a depotentiation bias to prevent runaway potentiation feedback loops leading to seizures [5]. Since synapses are frequently renormalized offline we incorporate a weak exploratory (potentiation) bias during the online phase which helps avoid local minima. 3 This is in line with experimental evidence showing increased cortical activity during waking [30].
Since computing the sum of synaptic weights is non-physiological, we draw on Theorem 1 and use the neuron's firing rate when responding to uncorrelated inputs as a proxy for w 1 . Thus, in the offline phase, synapses receive inputs generated as in the online phase but without repeated patterns. Note that (12) has a larger pruning effect on stronger synapses, discouraging specialization. Motivated by Remark 4, we introduce bias ( 3 2 − w j ) in the offline phase to ensure weaker synapses are downscaled more than strong synapses. For example, a synapse with w i = 0.5 is downscaled by twice as much as a synapse with weight w j = 1.0.
Regularized STDP alternates between 2 seconds online and 4 seconds offline, which suffices to renormalize synaptic strengths. The frequency of the offline phase could be reduced by decreasing the update factors α ± , presenting stimuli less frequently (than 7 times per second), or adding inhibitory neurons to the system.

Results.
A summary of results is presented in the table below: accuracy quantifies the fraction of spikes that co-occur with each pattern. Regularized STDP outperforms classical STDP on both patterns on average. It should be noted that regularized neurons were not only online for 20 seconds but also offline -and exposed to Poisson noise -for 40 seconds. Interestingly, exposure to Poisson noise improves performance.    1 provides a more detailed analysis. Each panel shows a 2D-histogram (darker shades of gray correspond to more trials) plotting accuracies on both patterns simultaneously, and two 1D histograms plotting accuracies on the two patterns separately. The 1D histogram for regularized STDP shows a unimodal distribution for pattern #2, with most of the mass over accuracies of 50-90%. For pattern #1, which has been "unlearned" for twice as long as the training period, most of the mass is over accuracies of 50% to 90%, with a significant fraction "unlearnt". By contrast, classical STDP exhibits extremely brittle behavior. It completely unlearns the original pattern in about half the trials, and also fails to learn the new pattern in most of the trials.
Thus, as suggested by our analysis, introducing a regularization both improves the robustness of STDP and enables an exploratory bias by preventing runaway feedback leading to epileptic seizures.

Discussion
The selectron provides a bridge between a particular model of spiking neurons -the Spike Response Model [20] with the original spike-timing dependent plasticity rule [5] -and models that are amenable to learning-theoretic analysis. Our hope is that the selectron and related models lead to an improved understanding of the principles underlying learning in cortex. It remains to be seen whether other STDP-based models also have tractable discrete-time analogs.
The selectron is an interesting model in its own right: it embeds reward estimates into spikes and maximizes a margin that improves error bounds. It imposes a constraint on synaptic weights that: concentrates rewards/spike, tightens error bounds and improves guarantees on spiking efficacy. Although the analysis does not apply directly to continuous-time models, experiments show that a tweak inspired by our analysis improves the performance of a more realistic model. An important avenue for future research is investigating the role of feedback in cortex, specifically NMDA synapses, which may have interesting learning-theoretic implications.

A.1 The perceptron
We describe the perceptron to facilitate comparison with the selectron.
The perceptron's loss function and learning rule are most naturally expressed when inputs and outputs take values in {±1}. We therefore present the perceptron in both ±1 and 0/1 "coordinate systems".
Let us first relabel inputs and outputs from 0/1 to ±1: A = 2X − 1 and B = 2Y − 1. Given input a, the perceptron's output is determined according to where w is a real-valued N -vector specifying the perceptron's synaptic weights.
Given supervisor σ : A → {±1} that labels inputs as belonging to one of two classes, define 0/1-valued loss function for the perceptron as The following learning rule converges onto an optimal solution if the classes are linearly separable.
The perceptron in "0/1 coordinates". For the sake of comparison, we reformulate the perceptron in "0/1 coordinates". If w j ≥ 0 for all j, the mechanism of the perceptron is (A.14) Similarly, we obtain loss function and learning rule Non-biological features of the perceptron. We highlight two features of the perceptron. First, learning rule (A.15) is not selective. If the perceptron classifies an input incorrectly, it updates its synaptic weights regardless of whether it outputted a 0 or a 1. It is thus not an output spike-dependent learning rule. The main consequence of this is that the perceptron is forced to classify every input. The selectron, by contrast, actively ignores neuromodulatory signals when it does not spike.
Second, the perceptron requires a local error signal. Multilayer perceptrons are constructed by replacing the sign(•) in (A.14) with a differentiable function, such as the sigmoid, and backpropagating errors. However, backpropagation requires two pathways: one for feedforward spikes and another for feedback errors. In other words, the perceptron requires local error signals. A dedicated error pathway is biologically implausible [33], suggesting that the cortex relies on alternate mechanisms.

A.2 Proof of Theorem 1
The theorem requires computing the second moment of a selectron's total current, given i.i.d. Bernoulli inputs. We also compute the expectation and the variance since these are of intrinsic interest. Lemma 5 (moments for i.i.d. Bernoulli inputs). For Bernoulli i.i.d. inputs on synapses, i.e. P (x j = 0) = p for all j, we have Proof. For the mean, For the variance, The expression for E[ w, x 2 ] follows immediately.
Theorem 1. Assuming the inputs on each synapse are i.i.d. Bernoulli variables with P (spike) = p, we have Proof. By Lemma 5, E w, The result follows since w 2 ≤ w 1 .

A.3 Proof of Theorem 2
We first compute the limit for STDP, and then move on to leaky integrate-and-fire neurons. Lemma 6 (fast time constant limit of STDP). The fast time constant limit of STDP, recall (5), is where δ 0 is the Dirac delta.
Eq. (A. 16) can be expressed in the shorthand

A.4 Proof of Theorem 3
To prove the theorem, we first recall an error bound from [24]. To state their result, we need the following notation. Let where C is a class of base classifiers taking values in ±1.
Let φ : R → R + be a nonnegative cost function such that 1 x>0 ≤ φ(x), for example φ(x) = and where L φ is the Lipschitz constant of φ, B is a uniform upper bound on φ(−f (x)y), and Rad C(X n 1 ) is the Rademacher complexity of C on data X n 1 .
We are interested in errors of commission, not omission, so we consider modified versions of (A. 17), and (A. 18), where we multiply by the indicator function 1 f >0 . This results in a discontinuous hinge function.
We therefore have to modify the above theorem. Theorem 8. Let f be a function chosen from C ω based on data (X i , Y i ) n i=1 . With probability at least 1 − δ, where L φ is the Lipschitz constant of φ, B is a uniform upper bound on φ(−f (x)y), and Rad C(X n 1 ) is the Rademacher complexity of C on data X n 1 .
Proof. We adapt the proof in [24]. By definition it follows that A). Thus, changing distributions from P (x) to Q(x) = P (x|f = 1), we can write n is the empirical distribution, P n (f = 1) = |{i:f (xi=1}| n and Q n ( Continuing, where we bound the two supremum's with high probability separately using Rademacher complexity and apply the union bound. The last inequality follows since φ ≤ B.
Remark 6. The change of distribution is not important, since the Rademacher complexity is bounded by the distribution free VC-dimension in Lemma 9.

Now let
where functions in F take values in 0/1.
Function class F ω denotes functions implementable by a two-layer network of selectrons S k = {n k } ∪ {n j : n j → n k }. The outputs of g j are aggregated, so that the function class F ω of subnetwork S k is larger than that of selectrons considered individually, i.e. F. Lemma 9. The Rademacher complexity of F ω is upper bounded by Rad n (F ω ) ≤ ω · 2(N + 1) log(n + 1) + 1 2 √ n .
Proof. Given selectron f w (x) = j w j · g j w (x), letḡ j := 2g j − 1 be the corresponding {±1}valued function. Then since w i ≥ 0 for all i. Thus, The Rademacher complexity of F is upper bounded by the VC-dimension, Rad(F(X n 1 )) ≤ 2V F · log(n + 1) n which for a selectron with N synapses is at most N + 1.

A.5 An alternate error bound with hard margins
For the sake of completeness, we prove Corollary 11, an alternate to Theorem 3 that bounds a symmetric 0/1 loss: The loss penalizes the selectron when either (i) it fires when it shouldn't or (ii) it doesn't fire when it should.
We replace the modified hinge loss in Theorem 3 with a hard-margin loss. Following [24], let The following corollary of Theorem 7 is shown in [24]. Corollary 10. Let f n be a function chosen from C ω . For any γ > 0, with probability at least 1 − δ, where V C is the VC-dimension of C.
We use Corollary 10 to derive an alternate error bound for the selectron. Introduce hard-margin loss 1 w x−ϑ ·ν(x)<γ = 1 if sign(w x − ϑ) = sign(ν(x)) and |w x − ϑ| > γ 0 else The following error bound exhibits a trade-off on the 0/1 loss of a selectron that is controlled by γ.
Proof. Follows from Lemma 9 and Corollary 10.
As γ increases, the size of the margin required to avoid counting towards a loss increases. However, the capacity term is multiplied by 1 γ , and so reduces as the size of γ increases. Thus, the larger the margin, on average, the higher the value we can choose for γ without incurring a penalty, and the better the bound in Corollary 11.

A.6 Proof of Theorem 4
It is helpful to introduce some notation. Given x ∈ X, let S j a = {x|x j = a}. Let ν jk=11 , defined by equation quantify the average contribution of neuromodulators when selectrons n j and n k both spike. Similarly, let ν jk=01 quantify the average contribution of neuromodulators when n k spikes and n j does not, i.e. the sum over x ∈ S j 0 . If upstream neurons are reward maximizers then spikes by n j should predict higher neuromodulatory rewards, on average, than not firing. We therefore assume ν jk=11 ≥ ν j=10 . (*) Theorem 4 Let p j := E[Y j ] denote the frequency of spikes from neuron n j . Under assumption (*), the efficacy of n j 's spikes on n k is lower bounded by Proof. Assumption (*) implies The result follows by direct computation.

A.7 Generation of Poisson spike trains
Spike trains are generated following [32]. Neurons have 200 synaptic inputs. Time is discretized into 1ms bins. At each time step spikes are generated according to a Poisson process where the rate varies as follows: 1. a synapse has probability r · dt of emitting a spike where r is clipped in [0, 90]Hz.
3. the rate of change ds of s is uniformly picked from [−360, 360]Hz.
The resulting spike train has an average firing rate of about 44Hz. Masquelier et al also add a mechanism to ensure each synapse transmits a spike after at most 50ms which we do not implement.
Repeated patterns are sampled from the process above for 50ms. The pattern is then cut-and-paste over the original Poisson spike train for 1 3 of the total number of 50ms blocks. The cut-and-pasting is imposed on a randomly chosen (but fixed) subset containing 1 2 of the neuron's synapses.