Mean Squared Projected Bellman Error

We have tested our method on the "star" Baird counter example [1]

ormjjvjj2D=v>Dv

limit distribution

Watkins and Dayan's Q-learning algorithm is an o-policy algorithm as thepolicy that is searched and evaluated is strictly greedy with respect to the current action values, butfor control the agent uses a"-greedy policy. This facilitates exploration as the agent is allowed tomake a random move with"probability to obtain representative samples and facilitate the searchfor a policy that generates high rewards.

4.3. Natural actor-critic algorithms

3.3. Compatible function approximation

Example 1.When using a REINFORCE estimator with a baselineb=0 in a scenario where there is only a single reward of alwaysthe same magnitude, e.g.,r(x,u)=c∈Rfor allx,u, then thevariance of the gradient estimate will grow at least cubically withthe length of the planning horizonHasVar{gRF}=H2c2HXk=0Var{∇θlogπθ(uk|xk)},(22)if Var{∇θlogπθ(uk|xk)}>0 for allk. Furthermore, it will alsogrow quadratically with the magnitude of the rewardc. The meangradient remains unaltered by the reward magnitudecin thisexample as the reward is constant.

or when acommon history of random numbers (Glynn,1987;Kleinman,Spall,&Naiman,1999) is being used (the later trick is known asthe PEGASUS method in reinforcement learning,

Kte= 10

moderate

5.11/79.32

Weuse simple 0/1 costs in defining the
function

We use simple 0/1 costs in defining the
function

capa-bilities of text-generation systems

Accordingly, we also found it use-ful to use a “curriculum beam” strategy in training

We therefore foundit necessary to pre-train the model using a standard,word-level cross-entropy loss as described in Sec-tion 3

When the gold sequence falls off the beamatt= 4, search resumes withS5= succ(y1:4), andso all subsequent predicted sequences havey1:4as aprefix and are thus functions ofh4.

succ(y1:t1)

If there was a margin violation,Stis con-structed as theKbest sequences assuming the goldhistoryy1:t1through time-stept1

BLEU scor

Above, the
(^y(K)1:t)term denotes a mistake-specificcost-function, which allows us to scale the loss de-pending on the severity of erroneously predicting^y(K)

We now define a loss function that gives loss eachtime the score of the gold prefixy1:tdoes not exceedthat of^y(K)1:tby a margin:

Ideally we would trainby comparing the gold sequence to the highest-scoring complete sequence

In practice,a simple beam search procedure that exploresKprospective histories at each time-step has provento be an effective decoding approach

rhtL rhtL+BRNN(wt+1;ht;rht+1L)

In this work we are agnostic to the form ofthe encoding model, and simply assume an abstractsource representationx.

When it comesto training RNNs, SEARN/DAgger has been appliedunder the name “scheduled sampling”

We run experiments on three very dif-ferent problems: word ordering, syntactic parsing,and machine translation

Loss-Evaluation Mismatch: training uses aword-level loss, while at test-time we targetimproving sequence-level evaluation metrics,such as BLEU

In this work, we introduce a modeland training scheme, based on the work ofDaum ́e III and Marcu (2005),

We call the resulting feature set Basic Pairwise RelativeOsets in Space (B-PROS) because it captures pairwiserel-ativedistances between objects in a single screen. Morespecically, a B-PROS feature checks if there is a pair ofBasic features with colorsk1;k22f1;:::;128gseparated byan oset (i;j), where13i13 and15j15.If so,k1;k2;(i;j)is set to 1, meaning that a pixel of colork1is contained within some block (c;r) and a pixel of colork2is contained within the block (c+i;r+j). Intuitively,B-PROS features encode information like \there is a yel-low pixel three tiles below a red pixel". The computationalcomplexity of generating B-PROS features is similar to thatof BASS, though ultimately fewer features are generated.Note that, as described, B-PROS contains redundant fea-tures (e.g.1;2;(4;0)and2;1;(4;0)), but it is straightforwardto eliminate them. The complete feature set is composed ofthe Basic features and the B-PROS features. After redun-dancy is eliminated, the B-PROS feature set has 6;885;440features in total (28;672 + ((31271282128)=2 + 128))

Basic Features:To obtain Basic features we rst dividethe Atari 2600 screen into 1614 tiles of size 1015 pixels.For every tile (c;r) and colork, wherec2 f1;:::;16g,r2f1;:::;14g, andk2f1;:::;128g, we check whether colorkis present within the tile (c;r), generating the binary featurec;r;k. Intuitively, Basic features encode information like\there is a red pixel within this region". There are 1614128 = 28;672 Basic features in total.It can be computationally demanding to work directlywith 160210 pixel screens with a 128 color palette. Tomake the screen more sparse, following previous work (e.g.[2, 3]) we subtract the background from the screen at eachframe before processing it. The background is precomputedusing 18;000 samples obtained from random trajectories

even Atari 2600 game

We present the first deep learning model to successfully learn control policies di-rectly from high-dimensional sensory input using reinforcement learning

The gamesQ*bert, Seaquest, Space Invaders, on which we are far from human performance, are more chal-lenging because they require the network to find a strategy that extends over long time scales.

raw RGB screenshots

Another,more stable, metric is the policy’s estimated action-value functionQ, which provides an estimate ofhow much discounted reward the agent can obtain by following its policy from any given state. Wecollect a fixed set of states by running a random policy before training starts and track the averageof the maximum2predictedQfor these states. The two rightmost plots in figure 2 show that averagepredictedQincreases much more smoothly than the average total reward obtained by the agent andplotting the same metrics on the other five games produces similarly smooth curves

Since the scale of scores varies greatly from game to game, wefixed all positive rewards to be1and all negative rewards to be1, leaving0rewards unchanged.Clipping the rewards in this manner limits the scale of the error derivatives and makes it easier touse the same learning rate across multiple games. At the same time, it could affect the performanceof our agent since it cannot differentiate between rewards of different magnitude.

The number of valid actions variedbetween4and18on the games we considered

the functionfrom algorithm 1 applies thispreprocessing to the last4frames of a history and stacks them

stbed that presents agents with a high dimen-sional visual input (210160RGB video at 60Hz)

Store transition(t;at;rt;t+1)inD

Note that when learning by experience replay, it is necessary to learn off-policy(because our current parameters are different to those used to generate the sample), which motivatesthe choice of Q-learning.

random minibatch

With probabilityselect a random actionatotherwise selectat= maxaQ((st);a;)

deepQ-learning

Since using histories ofarbitrary length as inputs to a neural network can be difficult, our Q-function instead works on fixedlength representation of histories produced by a function.

Note that this algorithm ismodel-free: it solves the reinforcement learning task directly using sam-ples from the emulatorE, without explicitly constructing an estimate ofE. It is alsooff-policy: itlearns about the greedy strategya= maxaQ(s;a;), while following a behaviour distribution thatensures adequate exploration of the state space. In practice, the behaviour distribution is often se-lected by an-greedy strategy that follows the greedy strategy with probability1and selects arandom action with probability.

Q(s0;a0;i1)

The Cartpole Regulator Benchmark

nother heuristic that we found helpful, is to add ’artificial’ training pat-terns from the goal region, which have a known target value of 0. This technique’clamps’ the neural value function to zero in the goal region, and we thereforecall it thehint-to-goal-heuristic

The Mountain Car Benchmark

Since we are interested in methods that can directly learn on real systems, ourpreferred measure of learning effort is the number of cycles needed to achieve acertain performance

They can be seen as a special form of the ’experience replay’technique [Lin92], where value iteration is performed on all transition experiencesseen so far.

Sample Setting of Costs

ul

c(sl,ul,s
l)

The consideration of the entire training information instead of on-line sam-ples, has an important further consequence: It allows the application of advancedsupervised learning methods, that converge faster and more reliably than onlinegradient descent methods. Here we use Rprop [RB93], a supervised learningmethod for batch learning, which is known to be very fast and very insensitivewith respect to the choice of its learning parameters

For example, a squared-error measure like the following can be used:error=(Q(s, a)−(c(s, a)+γminbQ(s,b)))2.Atthispoint,commongradientdescent techniques (like the ’backpropagation’ learning rule) can be applied toadjust the weights of a neural network in order to minimize the error

Manyof these problems arise, since the representation mechanism in a multi-layer per-ceptron is not local, but global: A weight change induced by an update in acertain part of the state space might influence the values in arbitrary other re-gions - and therefore destroy the effort done so far in other regions

e replaced the linear pair-wise function in Eq. (6) by a one-layer MLP, while keepingthe other settings identical

Counting numberscrare employed toweight the marginal entropies.

1st order MarkovTwo Laye

Joint training helps

by a one-layer MLP, while keepingthe other settings identica

define all pairwise interactions via

However, assuming allcounting numberscrto be positive, we can derive an al-gorithm that is able to interleave minimization w.r.t.wandmaximization of the beliefsb.

we require a sub-gradient w.r.t.w

The approximated non-linear structured prediction task

since amargin term is easily incorporated

parameter0is used to adjust the uniformityof the distribution

Weassume the space of valid configurations to be a productspace,i.e.,Y=QNi=1Yi, and the domain of each indi-vidual variableyito be discrete,i.e.,Yi=f1;:::;jYijg

iece-wise training is, however, suboptimal asthe deep features are learned while ignoring the dependen-cies between the variables of interest

Towards this goal, we propose atraining algorithm that is able to learn structuredmodels jointly with deep features that form theMRF potentials. Our approach is efficient as itblends learning and inference