Решение GridWorld с использованием Q-Learning и приближения функций

Question

Я изучаю простую проблему GridWorld (3x4, как описано в Russell & Norvig Ch. 21.2); Я решил это, используя Q-Learning и QTable, и теперь я хотел бы использовать аппроксиматор функции вместо матрицы.

Я использую MATLAB и пробовал как нейронные сети, так и деревья решений, но не получил ожидаемых результатов, то есть обнаружена плохая политика. Я прочитал несколько статей на эту тему, но большинство из них являются теоретическими и не зацикливаются на фактической реализации.

Я использую автономное обучение, потому что это проще. Мой подход выглядит так:

1. Инициализируйте дерево решений (или NN) с 16 входными двоичными единицами - по одному для каждой позиции в сетке плюс 4 возможных действия (вверх, вниз, влево, вправо).
2. Сделайте много итераций, сохраняя для каждой из них qstate и вычисленное значение q в обучающем наборе.
3. Обучите дерево решений (или NN), используя обучающий набор.
4. Сотрите обучающий набор и повторите с шага 2, используя только что обученное дерево решений (или NN), чтобы вычислить значения q.

Кажется, что это слишком просто, чтобы быть правдой, и действительно я не получаю ожидаемых результатов. Вот некоторый код MATLAB:

retrain = 1;
if(retrain) 
    x = zeros(1, 16); %This is my training set
    y = 0;
    t = 0; %Iterations
end
tree = fitrtree(x, y);
x = zeros(1, 16);
y = 0;
for i=1:100
    %Get the initial game state as a 3x4 matrix
    gamestate = initialstate();
    end = 0;
    while (end == 0)
        t = t + 1; %Increase the iteration

        %Get the index of the best action to take
        index = chooseaction(gamestate, tree);

        %Make the action and get the new game state and reward
        [newgamestate, reward] = makeaction(gamestate, index);

        %Get the state-action vector for the current gamestate and chosen action
        sa_pair = statetopair(gamestate, index);

        %Check for end of game
        if(isfinalstate(gamestate))
            end = 1;
            %Get the final reward
            reward = finalreward(gamestate);
            %Add a sample to the training set
            x(size(x, 1)+1, :) = sa_pair;
            y(size(y,  1)+1, 1) = updateq(reward, gamestate, index, newgamestate, tree, t, end);
        else
            %Add a sample to the training set
            x(size(x, 1)+1, :) = sa_pair;
            y(size(y, 1)+1, 1) = updateq(reward, gamestate, index, newgamestate, tree, t, end);
        end

        %Update gamestate
        gamestate = newgamestate;
    end
end

Он выбирает случайное действие в половине случаев. Функция updateq:

function [ q ] = updateq( reward, gamestate, index, newgamestate, tree, iteration, finalstate )

alfa = 1/iteration;
gamma = 0.99;

%Get the action with maximum qvalue in the new state s'
amax = chooseaction(newgamestate, tree);

%Get the corresponding state-action vectors
newsa_pair = statetopair(newgamestate, amax);    
sa_pair = statetopair(gamestate, index);

if(finalstate == 0)
    X = reward + gamma * predict(tree, newsa_pair);
else
    X = reward;
end

q = (1 - alfa) * predict(tree, sa_pair) + alfa * X;    

end

Любое предложение будет с благодарностью!

Answer 1

Проблема заключалась в том, что в автономном Q-Learning вам нужно повторять процесс сбора данных как минимум n раз, где n зависит от проблемы, которую вы пытаетесь смоделировать. Если вы проанализируете значения q, вычисленные во время каждой итерации, и подумаете об этом, сразу станет понятно, зачем это нужно.

На первой итерации вы изучаете только конечные состояния, на второй итерации вы также изучаете предпоследние состояния, на третьей итерации вы также изучаете предпоследние состояния и так далее. Вы учитесь из конечного состояния в начальное состояние, распространяя обратно значения q. В примере GridWorld минимальное количество посещенных состояний, необходимое для завершения игры, равно 6.

Наконец, правильный алгоритм становится:

1. Инициализируйте дерево решений (или NN) с 16 входными двоичными единицами - по одному для каждой позиции в сетке плюс 4 возможных действия (вверх, вниз, влево, вправо).
2. Сделайте много итераций (для этого примера GridWorld достаточно 30 игр), сохраняя для каждой из них qstate и вычисленное значение q в обучающем наборе.
3. Обучите дерево решений (или NN), используя обучающий набор.
4. Сотрите тренировочный набор.
5. Повторите процедуру с шага 2, используя только что обученное дерево решений (или NN), чтобы вычислить значения q, по крайней мере, n раз, где n зависит от вашей проблемы. Для этого примера GridWorld n равно 6, но вы получите лучшие результаты для всех состояний, если повторите процесс 7-8 раз.