I'm really getting stuck on creating a good reward function for my agent and could use some advice. I'll explain the setting for my question first:
Agent Description
The agent in question exists in a square grid world (of size (M x N)) that needs to be searched. Each grid location has a 'searched' or 'unsearched' status, and when the agent visits a grid location, the status of that location is set to 'searched'.
Agent State Space
The state of the agent is modelled by a (M x N x 2) tensor where the first channel is the binary matrix of grid statuses (1 for unsearched and 0 for searched) and the second channel is the agent's location matrix (1 for the location of the agent and 0 elsewhere).
Agent Action Space
The agent can move to any location on the grid in one time step, giving an action space shape of (M x N). Therefore the actions available to the agent are the same in any state and the number of actions is equal to the number of locations in the grid.
I am using Deepmind's fully convolutional StarCraft network to map the input state to the output action utilities.
Objective
The agent is placed in the center of the grid with all locations initialized as 'unsearched' and the agent must move throughout the grid and search all the locations while limiting the total amount of actions taken and total distance traveled. So for example, in a 9x9 grid the agent will want to only make 81 actions and its travel distance should also be 81 (as it should not make any diagonal movements).
Attempted Rewards
Subgoal Only: give the reward to an agent based only on attributes of the current state and action. So:
reward = new_location_status - (distance_traveled / max_travel_distance)
This did make the agent complete the search in optimal number of actions but even with a large amount of training it could not get an optimal total travel distance.
Shaped Reward: Using the previous reward as a 'subgoal scalar' I multiplied this by a function that exponentially increases as the agent gets closer to the goal state. Closeness to the goal state is measured by the sum of unsearched locations. Additionally there is an extra reward for reaching the goal state.
if goal state:
reward = 100
else:
goal_dist = 1 - (sum_of_unsearched / max_num_of_unsearched)^0.5
reward = goal_dist * subgoal_scalar
I thought this would improve my agent's incentive to converge to a goal state, but here the agent rarely reaches a goal state and many times chooses not to move for many actions.
So any input on improving the reward function would be great.
Testing Update
So as Matthew Graves mentioned below, it might be better to try using a more sensible $\alpha$ for the distance modifier of the subgoal only reward scheme.
Previously I had been using $\frac{1}{max\_travel\_dist}$ where $max\_travel\_dist$ was the maximum distance an agent could travel in one action given the grid size (i.e. the distance from one corner of the grid to the other). This caused the movement distance penalty to be very small in most cases.
After changing it to $\frac{1}{\sqrt{2}}$ I found that the agent was able to make much better decisions about its path trajectory for longer periods of time. This did not completely solve my issue, but it was definitely an improvement.
I also came to the realization that in my case, the movement of the agent should not be penalized differently just because it has a larger space. In my problem, the agent's optimal movement is always going to be one grid-cell at a time no matter the size of the grid. With the previous $\alpha$ I was constraining the distance modifier to be from 0 to -1, but by doing this I had created a construct that meant that a bad movement with travel distance of say 5 on a small grid would be extremely bad but on a larger grid would not be as significant and therefore the agent would not care as much to make such a movement.