What is a policy in machine learning?
A policy is a state-action mapping.  A 'state' is a formalism used in AI that represents the state of the world, i.e. what the agent's idea of the world is.  The action is, naturally, what action it should take in that state.  A policy just maps states to actions.  

One of the basic problems in AI is how to maximize reward over time at some task. 
 One strategy for the agent is to try to understand the system and predict the results of their actions, and the reward that would follow.  Another strategy is for the agent to try lots of things and record the results.  Either of these (eventually) allow the agent to calculate a good policy - and once it's calculated, the difficult computational work is done and the agent just has to 'look up' what action to take in each state.