Saturday, October 29, 2011

Designing an unbiased reward function

Still doing part 1 of the second MAS assignment. I've been wondering about the proper way to set the reward function. If we want our system to learn, the reward function should only include the objective of the game, right? If we start letting it know that collisions are bad or that moving closer to the prey is good, then what's the point of using Q-learning? You might as well just give it the perfect algorithm from the get go.

Is my thinking right? If it is, then the correct way to do this is to only give out reward when the prey is caught. Then, the Q-values should propagate the information. For example, since collisions would delay this reward, then the Q-values of moves that are likely to lead to collisions would become low in the long term. Does that make sense?

8 comments:

  1. Hey, I'm also working on this right now and these are my two cents:
    - giving penalty for collisions doesn't matter, because it just delays the goal
    - giving a small bonus for coming closer to the prey is very important. If you don't do it, then it takes a really really long time until they catch the prey by accident. My idea was that the reward for catching the prey should outweigh the bonus for coming closer to it.

    ReplyDelete
  2. Still, isn't the fact "getting closer to the prey = good" something that the predators are supposed to learn by themselves? I can see why it would take a ludicrous amount of time if you don't do it, but that doesn't change your fact that your learning is biased towards a specific (but of course correct) solution.

    ReplyDelete
  3. What we did was to restrict the Q-learning to a square area around the prey: when a predator is in this area it learns the correct behavior as you (Nikolas) suggested (reward only on the capture, punishment on collisions). When it is outside the "magic square" we just use an hard coded policy, which just make it get closer to the prey (in order to enter the square)

    ReplyDelete
  4. You can take two strategies to optimize the problem. One is to only give a reward (doesn't matter how high) when the predators capture the prey and zero otherwise. Then when you finally catch the prey you can update each previous state using the Bellman equation and this will result optimal times in the long run.

    However, the time it takes for the predators to capture the prey by random is pretty long. So a better way which also optimizes time is to give no reward for capturing and a negative reward for taking a step. What you can do is when you get to the new state you update the previous state. Now you are learning while you are capturing so it is online learning. (Check the sarsa algorithm in Sutton and Barto: Reinforcement learning, which can be found online for free)

    Everytime an action is taken that action will be devalued in Q which leads to the predators taking another action the next time they are in the same state. So predators will move away from their subspace instead of getting stuck.

    Also, to keep your space from exponentially exploding, start out by not only starting learning when you get close, but to stop learning when you get too far. You might even consider a negative reward for getting too far. This way learning is sped up.

    ReplyDelete
  5. I really like the idea of delivering negative punishment with each cycle. It's unbiased (since the objective is to minimise the number of cycles to catch the prey) and it also gives almost continuous feedback to the agents, which should speed-up the learning. I'll probably give out a small negative reward for each step and a big positive reward when the prey is caught. Otherwise, I'm afraid the difference in Q-values is going to be too small for the agents to take notice.

    I'll try not to "cheat" by using a default policy or giving out negative rewards when the predator is getting away from the prey. Instead I'll try to find ways to compress the statespace so that equivalent states have a single Q-value. That should make learning faster, right?

    Dario, giving out punishment on collision is not what I said; I said the opposite: that agents should learn on their own that collisions are to be avoided. As Lucian pointed out, this is achieved because collisions increase capture time, therefore they delay the capture reward, which makes the expected future reward of a state-action pair that leads to a collision lower than that of one that doesn't.

    ReplyDelete
  6. You could rotate and mirror the state space so that the agent is always in 1/8th of the board. This greatly reduces the size of the state space and is also an easy mapping. If you use a negative reward for each step it is in principle not necessary to use any other reward since Q will converge to the optimal policy given an infinite amount of episodes.

    However, do watch out for the most common error which is that each state has to be visited an infinite amount of times for convergence to occur. So random begin states with perhaps a random first action results in SARSA conforming to this.

    Use a discounted future reward or use negative reward for the steps.

    http://webdocs.cs.ualberta.ca/~sutton/book/ebook/the-book.html

    My method is SARSA which is an on-policy implementation of TD

    Protip: if you can, implement traces to increase the learning rate:
    basic idea is to update all states depending on their current trace and let the traces decay in each step (which is basically just an update of all visited states)

    These traces should be given to a state-action pair so that each action can have its own trace. If you visit a state you have already visited, set the trace of the new action in that state to 1 and all other traces in that state to zero (this is replacing traces)

    ReplyDelete
  7. Also: it could be that if the predators are on a maximum distance of the prey but close to each other that they learn to collide since they will always end up closer to the prey. So collisions could end up as a tactic given enough time. If this is still unwanted you need to give a negative reward to collisions. If not you could describe this as normal emergent behavior.

    ReplyDelete
  8. My plan was to rotate and mirror the state space so that equivalent states would get a single q-value. Additionally, I wanted to count only one state if the ending square of two predator actions is the same, given specific prey and other-predator positions.

    Since time is ticking away though, I'll probably just mention these in the report and put the predators on autopilot until they are close enough to the prey.

    You are right that setting a negative reward for each step is the same as setting a positive reward for catching the prey, so implementing both is redundant. But as you said, this is only true when the system converges. In the meantime, I fear that a state with 26 negative rewards might not look that much better than a state with 27 negative rewards to the algorithm.

    As for collisions, you are right. My intention is just not to bias the predators in learning. That's why I don't want to give out rewards/penalties for any action other than the main objective. If they learn to collide in some cases and that leads to better capture times, then good for them; who am I to tell them it's not right?

    I'm not sure I understand the differences between all the reinforcement learning algorithms, since I've never worked on the subject before and I didn't have any time to study it now. So, I'm just implementing whatever's in the book and pray to that it's about right: Right now, I think I'm doing what you described as online learning. After each step, I update the q-value of the previous state then use a Boltzmann distribution to pick one of the available actions based on the q-value of the current state.

    ReplyDelete