Reinforcement Learning Study - 3 (Value Iteration, using Bellman optimality equation)

 Value Iteration method (grid world)

 In last post, we've solved the grid world problem with 'policy iteration' method that uses bellman expectation equation. This time, we'll solve the problem with 'value iteration' method that uses bellman optimality equation.




 bellman optimality equation.


1. Like the previous method, initialize all value of the table with 0.

2. Evaluate each state with bellman optimality equation like below

    (example of s0).


3. repeat the process '2'
  After repeating the process, the value table will be as above.
Each value of the table represents the number of steps left to the goal when following the optimal path. and in this case, the optimal policy can be obtained by gridy way.






Prediction in model-free evironment

 So far, we've dealt with MDP problem where we do know all about environment(model-based MDP). But in real world, there are few such problem. There are two methods to evaluate state (Prediction) in model-free problem, MC(Monte Carlo) and TD(Temporal Difference). Here, the 'model' means reward funciton(R) and transition probability function(P). In other words, we don't know about R and P in model-free MDP.


Monte Carlo Prediction

 In Monte Carlo method, agent learn the environment from whole an episode through direct action (cannot plan). So, for updating value of states, each episode should be ended. when each episode is ended, the agent evaluate states with cumulative rewards.

 Evaluating from an episode, each state value can be calculated by following equation.




and
meaning that adding a certain percentage of new value to the original value.
And writing it differently, it is gonna be as follow.


I've tested MC method if this method could solve prediction problem.
the equation above could be written in pseudo code like

...
for (the number of learning episode)
    while ( an episode ends)
        record an episode history(array)

    #when an episode ends, check the history arrary from the end point.
    for (history)
        value[x][y] = value[x][y] + alpha * (g_t - value[x][y])
        g_t = reward + gamma * g_t
...
'g_t' refers to cumulative rewards.



 The result is as below.

The result looks pretty well.



Comments

Post a Comment

Popular posts from this blog

Reinforcement Learning Study - 7

Image
Deep Reinforcement Learning  In real world, states or action space is too big to record all information about the model in (value) table. So as to generalize the information, the most powerful generalization tool(function), Neural Network is used. A node is fundamental component of neural network, and each node linearly combines(WX + b) the inputs entering the node and then outputs them by applying a nonlinear function(sigmoid, ReLU etc...).   Value-based agent  value-based learning is method where neural netwrok is used to predict value function. In neural network, 'Loss function' is used to update parameter of neural network. Loss function is defined as the difference between the predicted value and the real value.  In Q-learning, value function is defined  .  so Loss is defined as below. In fact, in the above eqation, because we don't know real value Q, we can't use that equation. So, here we have smart way to solve this problem. That's the expected val...
Read more

the US and British attacks on Houthi and the impact of stock market

Image
the US and British attacks on Houthi and the impact of stock market  The US and UK launched airstrikes on more than a dozen sites used by the Iranian-backed Houthis in Yemen. This was a significant military response to the Houthis’ persistent campaign of drone and missile attacks on commercial ships in the Red Sea. The Houthis, backed by Iran, run most of the west of Yemen and control its Red Sea coastline. The strikes have raised fears of a broader escalation of the conflict in the region. The attacks led to an increase in oil prices. Brent jumped on fears there would be more disruption to shipping, and that the conflict could expand into a broader regional conflagration. Global benchmark Brent was trading around 4% higher. The rise in oil prices was driven by the market’s perception that this is an escalation of the conflict. The impact of rising oil prices on the stock market The impact of rising oil prices on the stock market is complex. An increase in oil prices usually lowers...
Read more

U.S. Stock Outlook 2024

Image
  Let's take a look at the 2024 U.S. stock outlook. To take a look at the 2024 U.S. stock outlook, we'll take a look based on recent announcements from Morgan Stanley and Forbes. What is Morgan Stanley? Morgan Stanley is an American multinational investment banking and financial services company headquartered at 1585 Broadway in Manhattan, New York. Morgan Stanley also offers a range of prospects to help raise, manage, and distribute funds. Morgan Stanley's Outlook Morgan Stanley said 2024 is an overvalued stock, so analysts' estimates of corporate earnings may be too optimistic given the easing of U.S. economic growth. Also, it said the market may be overestimating the number of Fed rate cuts in 2024. On the one hand, the stock market will provide investors with "greater opportunities," it said, "and the market has been efficient at rewarding and punishing the right stocks for the right fundamental reasons." Analysts predict the S&P 500 will end...
Read more