TL;DR
If MDP is the game, then value functions are the scoring rubrics. It decides how your "gameplay score" is calculated. (Though a caveat, I must say, it does not actually decides who win, it is up to something else (no spoilers yet) that makes the call, or how they choose to interpret this score.)
Value Function
RL is about using value functions to estimate...
Value function is a function that estimate how good an agent is gonna perform,for the rest of the game, if given the current situation (perform certain action or in a certain state).
The "for the rest of the game" is important here. Because we are only given limited information (the "present"), and we are trying to predict the future using the present.
Policy (π), aka a way of acting, can be think of as a playing style, a habit, or tactic book. It is the final product of RL. And what we are trying to improve / optimize.
Example: npc (agent) enters state See Player, 80% time: attack, 20% time: retreat. (<- this is the policy just for 1 state. policy is for all states and each state is different)
State-Value Function Vπ(s) - calculate how good the agent is gonna perform, for the rest of the game, if it is currently at a given state s (ex. agent locate nearing the exit is better than agent getting stuck at the corner, if the goal is to leave the maze)
Action-Value Function Qπ(s,a) - calculate how good the agent is gonna perform, for the rest of the game(episode), if the agent were to perform certain action a under current state s (ex. when approaching the exit door (state), keep going (action) has higher score than turn around (action)
Dynamics
Environment's Dynamic Function p(s',r | s, a) - calculate the probability that you land in the next state s', got given reward r, given that you were in state s and took action a.
p is the rulebook + dice of the game.
Using Monopoly as the example,
It tells you the odds of each outcome:
s' - the next square you land on
r - money you'll gain or lose
Given your:
s - current square you're in
a - action you take (edit: i realize Monopoly is a bad example here, for a, because you move first, then take action, like buy a property or something. But for this case it is the action you take while you'll in this current state)
Bellman's Equation
is basically a state-value function in a different form. (this took me forever to wrap my head around)
A form that is usable, by us.
Think state-value function as the theory (looks ahead the entire future)
and Bellman's equation as the application (looks ahead just one step, aka the next state s')
Bellman's equation is the logic to value a square, a.k.a how good it is to stand on this square, and go from there for ONE STEP.
It takes in account of:
(A) the current rewards, plus
(B) the rewards of being in each of the possible future states, by considering all possible actions. (and take the average) (also taking a discount γ of this value since it is the future)
The point of RL is not just about how to win (complete the task), but how to excel at it (Optimal Policy).
Policy that gets higher rewards means better policy.
Optimal Policy π* - is π that yields the best reward (a.k.a highest v for every state)
which has the v* and q*
Bellman "optimality" Equation:
q* is the expected return (aka reward) when whenever action is taken, at a given state, according to optimal policy
v* is the reward when best action is taken (so v* = the highest q*)
Example:
Game: Slot Machine (assume each "play" is independent so s does not matter)
Action space: Gamble, or Stay safe.
Task: win as much money as possible
Rubric: if gamble, you win $20 for 20% of time, win $0 for 80% of the time. If stay safe, win $5 100% of the time.
q*(s, safe) = 5
q*(s, gamble) = (0.2*20)+ (0.8*0) = 4
5>4
so v* = q*(s, safe) = 5
In real world senario getting to absolute optimal is hard. that's why we use big computer to get as close as possible.
Human Proof
Original Note