The problem is when you do [quote=“jtremblay, post:12, topic:1097”]
yhat[j] = y
[/quote]
>>> print 'yhat[j] size: ', yhat[j].size(), 'y size: ', y.size()
yhat[j] size:  torch.Size([1]) y size:  torch.Size([1, 1])

so this is causing issues when backpropping.
If you just change that line to:
yhat[j] = y[0]

everything works properly.
Full code (same as yours, except for that one line):
import numpy as np
import torch
import random
import torch.nn as nn
import torch.nn.functional as F
import torch.optim as optim
import torch.autograd as autograd
from torch.autograd import Variable
import torchvision.transforms as T

class Policy(nn.Module):
    def __init__(self):
        super(Policy, self).__init__()
        self.fc1 = nn.Linear(5,5)
        self.lstm = nn.LSTMCell(5, 2)
        self.fc2 = nn.Linear(2,1)

    def forward(self, x, hidden):
        y = self.fc1(x)
        hx,cx = self.lstm(y,hidden)
        y = self.fc2(hx)

        return y, hx,cx


model = Policy()
optimizer = optim.Adam(model.parameters())

step = 1

for i in range(100):
    yhat = Variable(torch.zeros(step,1))
    target = Variable(torch.zeros(step,1))
    target[-1,0] = 1
    cx = Variable(torch.zeros(1,2))
    hx = Variable(torch.zeros(1,2))
    hidden= [hx,cx]

    for j in range(step):
        x = Variable(torch.zeros(1,5))
        if j is 0:
            x += 1
            x = Variable(x.data)
        y, hx,cx = model(x,hidden)
        # print (hx.data.numpy())
        hidden = (hx,cx)
        print ('y',y)
        print ('hidden',hidden)
        yhat[j] = y[0]

    print ('done - the last output should be one')
    #learning   
    optimizer.zero_grad()
    error = (yhat-target).pow(2).mean()
    print (error)
    error.backward()
    optimizer.step()

Gives the following output:
('y', Variable containing:
-0.7611
[torch.FloatTensor of size 1x1]
)
('hidden', (Variable containing:
-0.1136  0.1655
[torch.FloatTensor of size 1x2]
, Variable containing:
-0.2690  0.3413
[torch.FloatTensor of size 1x2]
))
done - the last output should be one
Variable containing:
 3.1013
[torch.FloatTensor of size 1]

('y', Variable containing:
-0.7580
[torch.FloatTensor of size 1x1]
)
('hidden', (Variable containing:
-0.1126  0.1623
[torch.FloatTensor of size 1x2]
, Variable containing:
-0.2672  0.3351
[torch.FloatTensor of size 1x2]
))
done - the last output should be one
Variable containing:
 3.0906
[torch.FloatTensor of size 1]

('y', Variable containing:
-0.7549
[torch.FloatTensor of size 1x1]
)
('hidden', (Variable containing:
-0.1115  0.1591
[torch.FloatTensor of size 1x2]
, Variable containing:
-0.2654  0.3289
[torch.FloatTensor of size 1x2]
))
done - the last output should be one
Variable containing:
 3.0798
[torch.FloatTensor of size 1]

....


I trained it for large number of iterations and the loss converged.