Markov Decision Processes Part 2: Discounting

As discussed in the previous post, four main components of a MDP include state, action, model and rewards. In MDPs, rather than focusing on immediate rewards, the agent tries to maximize the total future reward. A particular action might yield higher immediate reward, but it might not be best in the long term. This makes it challenging to find an optimal policy for a MDP. To proceed in this direction, we need to calculate the expected cumulative reward an agent would receive in the long run and then choose an action with the maximum expected value.

In this post, we will formulate a way to calculate the cumulative reward an agent would receive in the long term, denoted by Gt. It is also called a return. If the sequence of rewards earned after time step t is denoted by Rt+1, Rt+2, Rt+3, and so on, then the return is given by

Gt = Rt+1 + Rt+2 + Rt+3 + ..... + RT

Where T is the final time step. If a MDP does not have an end-state or a terminal state, then, the return is equal to

Gt = Rt+1 + Rt+2 + Rt+3 + ..... + inf

This is very straightforward and hence self-explanatory. But the formula defined above has some shortcomings. Let me explain it to you with the help of a real-world scenario. You have to select one of the two given options :
Option 1 -  I will give you one chocolate every day for ten days.
Option 2 -  I promise you to give ten chocolates after ten days.
Which option will you choose? You will obviously choose option 1, primarily because of the presence of uncertainty in option 2. You tend to prefer things right away rather than waiting for it because you never know what might happen later (What if I go bankrupt and cannot buy you the ten chocolates I promised).

In the picture below, an agent is provided with two different paths to choose from. In the left path, the robot gets the diamonds in each step and in the other one, it gets all the diamonds at the end. If we apply the equation described above, we will get the same returns in both cases. But, the above discussion tells us that this should not be the case. We prefer to accrue earlier rewards more than later rewards. Sooner rewards have a higher utility than later rewards.
In order to formalize this, we use the concept of discounting. Discounting makes sure that our agents would prefer getting rewards earlier rather than later. In this concept, we decay the value of later rewards exponentially so that they worth lesser than the earlier rewards. Discounting factor is denoted by γ (gamma) = [0,1]. The discount rate determines the present value of future rewards. The future rewards are discounted because of the presence of uncertainty. Farther away the reward is in the future, more the uncertainty and hence more is it's discounting. The modified equation for the return is given by,

For a value of γ = 0, the agent is short-sighted, i.e. it is only concerned with immediate reward. All future rewards are neglected in this case.  For a value of γ very close to 1, the agent becomes more far-sighted and takes into consideration all rewards almost equally. For a continuous task where there is no terminal state, the use of discounting is very useful. For a value of γ between 0 and 1, Gt forms a geometric progression whose sum is finite.

References: 
1. CS188 Introduction to Artificial Intelligence, UCB
2. Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.

Comments

Post a Comment

Popular posts from this blog

The move_base ROS node

Image
move_base package provides the move_base node which is a major element of ROS Navigation stack. It moves the robot from its current position to a goal position. When path planning is done, the user gives uses the 2D Nav Goal in RVIZ to specify the goal position and orientation. This position (x,y,z) and orientation(x,y,z,w) are actually published in move_base/goal topic. The move_base node links together a global and local planner to accomplish its global navigation task. The Global Planner It is in charge of calculating the safe path in order to arrive at goal pose. Note that the path is calculated before the robot starts moving so it will not take into account the laser readings while moving i.e. unscanned obstacles that are not in the map. Navfn Planner The Navfn planner is the most commonly used global planner for ROS Navigation. It uses Dijkstra's algorithm in order to calculate the shortest path between the initial pose and the goal pose. Carrot Planner This plann...
Read more

Three Wheeled Omnidirectional Robot : Motion Analysis

Image
A Three-wheeled omnidirectional robot is capable to moving in any given direction without rotating by giving velocities to the three wheels in a certain ratio. All motors are situated at an angle of 120 degrees from each other. f B ,  f L ,  f R  are for back , left and right wheel respectively. a x  and a y  are accelerations in X R  and Y R  axis in Robot frame and w is the angular velocity in Robot frame. Hence putting the values of alpha and making it into a matrix form we get : As we need to obtain the f values, we will invert the matrix. We need  a x  , a y  and w is the world frame, so we apply transformation. The transformation angle is    α 1  = 30 degrees.  Putting this in the previous equation, Multiplying the two matrices, we get the final relation as : For example, if you want to move the robot along X axis(world frame), put  a x W  = 1 , ...
Read more

Overview of ATmega328P

Image
While reading about the ATmega328, I came a across a lot of stuff which I would like to share here. There is a humongous amount of information available in its datasheet. Introduction ATmega328 is a single chip micro-controller created by Atmel. It has a In-System Self-programmable Flash memory of 32 KB, SRAM of 2 KB (2048 bytes) and EEPROM of 1 KB (1024 bytes). It has a 8-bit AVR CPU type which means they can process data in 8-bit chunk as its data bus is 8-bit wide.   It contains 23 general purpose I/O pins and 32 general purpose working registers. It has 32 single-byte registers and 8-bit RISC (reduced instruction set computer) devices and hence the name 328. The P is for ' picoPower '. It has 3 flexible timer/counter with compare modes, internal and external interupts , 6-channel 10-bit A/D converter , programmable watch dog timer with internal oscillator and 5 software selectable power saving modes. Digital communication peripherals include 1-USART, 2-SPI and 1-...
Read more