finite MDP (finite Markov Decision Process)
Agent - the learner, or decision maker (think robot)
Environemnt - the enclosed space that the agent interact with (think a maze with an exit)
Agent perform a range of actions (ie. walk forward, left/right, jump, destory obstacles...) with no clear instruction.
Environment gives agent reward when preferable state is reached (state is like a given situation in the environment, such as, the agent stepped closer to the exit)
Agent's goal is to maximize cumulative reward in a given training session (AKA episode)
You can also think of MDP as a finite state machine, where States of environment is the node, the arrow connecting the nodes are agent's actions, and the conditions are the rewards.
The "finite" means there is a finite prssibility of state and rewards. What they also called a finite probablity space of S x R x A.
Rewards
The reward isgnal is your way of commuicating to the agent what goal want achieved, not how you want it achieved.
Returns = Reward_t + Reward_t+1 +... + Reward_T
Return is cumulative rewards over the entire episode.
Terminal State = end of an episode
Endless Episode
aka. Continuing tasks. Think balacing a pole.
To fairly grant rewards, we give a discount for future rewards. (the further, the less)
This way we encourage the agent to reach the goal faster. (aka successfully balacing the pole without much wabbling)
Gamma is the discount factor (between 0 and 1)
big gamma -> less discount -> encourage long term rewards
small gamma -> more discount -> encourage immediate reards
More on Rewards
Rewards is hard to define by nature (unless it's well-defined problem with straighforward solution)
the main chanllenge is sparse reward. (aka hard for agents to stumble upon the correct action that triggers the rewards, it's like having monkey using typewritter to write Shakespare)
Delivering small none-zero rewards that nudge agent to do the right thing is good. But should avoid directly reward certain actions.
Lots of trial & error is common to produce acceptable results.
Some solutions:
1. make the problem easier first (so it is easier for agents to trigger rewards), then slowly increase difficulty, until it matches the real senario.
2. Imination Learning. ("Reverse reinforcement Learning")
3. Automate the trail & error process for searching good reward function (i.e. the Eureka Paper?)
4. augment value-function aproximation?
Human Proof
Original Note