0
$\begingroup$

I have done a lot of research on the internet about Reinforcement Learning and I found encountered methods of Reinforcement Learning: Q-Learning and Deep Q-Learning. And I have developed a vague idea of how these two work.

Before I knew anything about Reinforcement Learning this is how I thought it would work:

Suppose I have 2 virtual players in a game who can shoot each other, one of them is a decent playing hard-coded/pre-coded AI, and the other one is the player I want to train (to shoot the other player and dodge his bullets), the aim of the game would be to get the greatest net score (shots you hit minus shots you took) within 1 minute (a session), and you only have 20 bullets.

A basic idea of the the game I mean

You have 3 actions, move left-right (0 = maxleftspeed, 1 = maxrightspeed ), jump (0=don't jump, 1=jump), shoot (0 = don't shoot, 1 = shoot).

What I thought was, you could create a basic Feed-Forward Neural Network use the enemy's position and his bullet(s)'s position(s) and bullet direction(s) for the input layer and the action being taken will be given by the (3 nodes in the) output layer.

The untrained player starts off with a randomized algorithm, then (for back-propagation) at the end of each session it modifies one of the parameters by a bit in the neural network, and a new session is started with the slightly modified NN. If this session ends with more points than the previous session, it keeps the changes and makes more changes towards that direction, otherwise, the changes are redone, or possibly reversed. I would visualise this as gradient descent similar to that of Supervised learning.

So my questions are:

  • Is something like this already out there? What is it called?
  • If nothing like this is out there, could you give me any tips to optimize this method or point out any key points I should keep in minds while carrying this out?
  • Since I have written this game, I have control over the speed of the actions, but if I did not, I know this AI would take ages to learn, so is there any way to make the learning faster while still keeping the basic idea in mind?
  • How exactly is this different from deep Q-learning (if it is)?

Thanks in advance!

$\endgroup$

1 Answer 1

2
$\begingroup$

Is something like this already out there? What is it called?

There are three algorithms that have similarities to yours, but are not identical:

  • NEAT, which is an evolutionary method that mutates neural networks and compares their fitness across populations of variations.

  • The Cross Entropy Method, which trains a single, initially randomly behaving, neural network based on the outcomes of its best performances.

  • REINFORCE is a policy-gradient method that trains a neural network after completing games based on the results of every game. It is very similar to your idea, except that it includes the maths/logic to sample a full gradient of all NN parameters in a single go. It does not require making a test change to a single parameter, but can calculate the full error gradient at once. Usually, however, to reduce noise and effects of correlation within a game, multiple gradients are collected from different games and averaged.

The main similarity in each case is that you are performing a policy search, and training based on selecting outcomes that are closer to your goal after trials. A policy-based approach means that your NN represents the choice of action directly. A policy is a function that converts knowledge of the state of an environment into an action.

If nothing like this is out there, could you give me any tips to optimize this method or point out any key points I should keep in minds while carrying this out?

Your suggested method is not exactly the same as any of the suggested algorithms, and may have a problem with performance due to this:

The untrained player starts off with a randomized algorithm, then (for back-propagation) at the end of each session it modifies one of the parameters by a bit in the neural network, and a new session is started with the slightly modified NN. If this session ends with more points than the previous session, it keeps the changes and makes more changes towards that direction, otherwise, the changes are redone, or possibly reversed. I would visualise this as gradient descent similar to that of Supervised learning.

This single parameter change search is likely to be slow, probably unusably so for any reasonably-sized neural network. Effectively you would be performing a single parameter step for a very noisy gradient descent algorithm, per full play of the game. All of NEAT, CEM and REINFORCE are likely to perform much better than this (and none of them are state-of-the-art).

is there any way to make the learning faster while still keeping the basic idea in mind?

Instead of sampling the total reward at the end of each game and generating a single parameter's gradient, use a deep reinforcement learning method that works with full gradients.

You might find REINFORCE interesting, as it logically the idea closest to yours, and it leads to some state-of the art methods such as A3C, DDPG, PPO . . . the main problem with all of these being that the maths is hard to understand, even though the implementations can be simple you may be left scratching your head as to why they even work. However, if you are happy with just seeing the policy gradient theorem as some maths which completes your idea, then it is there for the taking.

Otherwise, if your goal is to implement something you understand the internals of fully, I would suggest that you search for a tutorial on deep Q learning, maybe something that implements DQN, as the maths and intuition behind it are more accessible.

How exactly is this different from deep Q-learning (if it is)?

Both your suggested method and Q learning can probably be considered "deep reinforcement learning".

The main differences are:

  • Q learning is a value-based method, and yours is a policy-based method

  • Q learning is off-policy (it learns best overall actions even whilst exploring other possibilities) whilst your approach is on-policy (the actions it learns to take are the same as the actions it takes during exploration)

  • Deep Q learning updates all the parameters of the NN on each time step, whilst you will be updating a single parameter per episode. That makes Q learning far more sample efficient than your suggested approach.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .