Skip to main content

AI Simplified 2 : Bellman and Markov

Bellman equation 

It's named after Richard Bellman and is defined as a necessary condition for optimality. It is associated with the mathematical optimization method known as dynamic programming. The deterministic equation is listed below: 

V(s) = maxₐ  (R(s,a) + ɣ(V(s'))


maxₐ: represents all the possible actions that we can take.
R(s, a): The reward of taking an action at a particular state.
ɣ: Discount. Works like the time value of money.

 You can see the dynamic programming aspect as we call the same method on s'. So it will recursively operate to solve the problem.

Deterministic vs non-deterministic: Deterministic is definite, there is no randomness whereas non-deterministic is stochastic.

So above we were not adding any randomness (deterministic) but nothing in this world is truly predictable, let's add randomness. Whereby each step is not so certain to be done (adding probability). It makes our agent more natural (being drunk! lol) so that means maybe our agent will have an 80% probability to listen 10% to go another way and 10% to go another way.

Markov Decision Process 

This is essentially the Bellman equation but catering for non-deterministic scenarios. We will loop through each possible next state, multiply the value of that state by its probability of occurring and sum them all up together.

The Markov Property

This property states that the past does not matter - it only looks to the future and the present. So it only looks to the current state. It also helps us save our memory since we do not need to save past states. 

Concept

A stochastic process has the Markov property if the conditional probability of the future states of the process depends only on the current state. The MDP provides a mathematical framework for modeling decision making where outcomes are partly random and partly under the control of the decision-maker. It adds more realism and perfection to the Bellman equation. It changes the Bellman from being deterministic to be non-deterministic.

The equation

S: This is the state our agent is in.
Model : T(s,a, s') ~ Pr(s'|s, a). Also known as the transition model. Determines the physics or rules of the environment and the function produces the probability.
Actions: A(s), A. Things you can do in a state.
Reward : R(s), R(s,a), R(s,a, s' ) Represents the reward of being in a state. The main focus is R(s). This is the reward function.
Policy: 𝝿(s)→a, 𝝿*. The solution to an MDP. It differs from the plan because a plan is just a sequence of events whereas the policy tells you what to do in any state. Shows the key-value pairs.

V(s) = maxₐ (R(s,a)+ ɣ∑s' P(s, a, s') V(s'))


Living Penalty- It's a negative reward for being in a particular state. The main incentive for this is for the agent to want to finish the game as quickly as possible.



Labels:

Comments

Post a Comment

Popular posts from this blog

Gentlest introduction : The Cloud

How it began To me the concept of cloud started when people began virtualizing their systems using the like of Virtual-box and VMware. What bough this a;long was the evolution/advent of technology which made it possible for software so simulate hardware. Originally software could not simulate hardware drivers but the moment that became possible- virtualization was born. A few years after- companies started offering this virtualization at a much grander scale and Infrastructure as a service was born. Lets get down to the three cloud components namely: Infrastructure as a Service (IAAS) This outsourced hardware meaning that one noways noes not need to setup servers, air-con and the like of access control but could 'rent' from someone and one of the great things about this was that a backup not only meant software but also meant hardware (as software could now simulate hardware) so recovery in case of disaster became easier. Platform as a Service (PAAS) This is ...
Post a Comment
Read more

Deploy Django app online for free!

So after a number of lines of code, brilliance and dreaming. Your next dream is for the world to see. Of course you can walk around with your computer and doing a 'manage.py runserver' But cumon guys, lets embrace the cloud. Not like this guy though! I choose to deploy on  PythonAnywhere . So you ask why? 1) Free amazing support - You actually talk to a live human ! 2) Easy - Very easy 3) Affordable - As you scale up, it gets way better! So by now I assume you are already on a version control system (So I will not waste much energy on that one). Maybe Ill someday write on my two favs  Github  and  Bitbucket . STEP 1: Create an account on pythonanywhere. Kindly note that your username will be included in your apps url. So it will be like : " yourUsername .pythonanywhere.com" STEP 2: Select other and set a bash console. STEP 3: Push your code from version control This will push from (in my example) github to your pythonanywhere. You...
1 comment
Read more

Making money with the falling rand: Lessons from Zimbabwe

It is no secret that the rand is falling like there is no tomorrow. This year alone it has fallen by over 18%. And if you look closely, at the last 3 years- it has fallen by 35%! This is not neglecting the economic setup where the slightest thing leads to ‘ toi toi. ' This trend of continuous striking and pay rate increase bargains has created such a vicious cycle. Prices rise, people strike, economy starts going through stuff. And we back at square one. We all know for sure that this cycle is bad. Zimbabwe and South Africa might not be different soon, only difference being that Zimbabwe chased the farmers, South Africa is chasing stabilisation. (Maybe the paradox of thrift  (prompted by the large population) will save them! Hope so.) In Zimbabwe 2008, a lot of people made a lot of money from ‘burning money’. This was whereby people took advantage of the bank rate versus the ‘streets’ rate of forex. The streets rate for forex was lower than the bank rate. Problem wa...
Post a Comment
Read more