UBC Wiki - User contributions [en]

Course:CPSC522/MarchApril2018

2018-04-27T18:29:56Z

AINAZHAJIMORADLOU:

==March/April Assignment==
Your third and final assignment is to create a hypothesis related to the course and test it. Your result should describe the hypothesis and whether it works. The reader should be able to understand the background, what the the hypothesis is, whether the hypothesis is true, and the evidence you used to come to this conclusion. Your hypothesis can be theoretical or practical.

==Extra Rules==
* You need to follow the rules on the main page and you should follow the guidelines there.
* Each page can have multiple authors (so it can be a group project).
* You need to add your page to the table of contents in a position that makes sense. Fell free to edit and change the structure of the table of content to give it a coherent structure.
* You will need to give a presentation of at most 4 minutes + 2 minutes for questions for each person (so if you have a group of 3, for example, you need a coherent presentation of 12 minutes where everyone participates); do not go over! If you would like to give a presentation during term time please contact David. For those who do not want to present during class time, we will have a presentation session during exam time.
* Please choose a topic that is different from other courses that you have done (or else you need to negotiate with the instructors to make sure you are not counting the same work multiple times).
* You should refer to wiki pages and to other research papers as appropriate.
===Key Dates===
* April 3 - last day to choose pages
* April 16 - First Draft ready for critiquing. Each page has a number Mn on the home page.

- If a page M(n) has a single author, you will critique pages M(n-1), M(n+1) and M(n+6) where each addition is mod 15 (as there are 15 pages numbered M0 to M14).

- If a page M(n) has multiple authors, you will between you critique pages M(n-1), M(n+1), M(n+6), M(n+8), M(n+10), M(n+13) all mod 15. You decide between you who does which pages.

Write your comments in the discussion tab of the page. Please give constructive feedback --- give the sort of feedback you would like to receive --- and answer the questions on the evaluation page. Please feel free to respond to them there too, and actually have a discussion. The critiques are not meant to be anonymous; you are meant to be helping each other.
* April 17 10:00am-12:30 - Presentations
* April 19 - Critiques due
* April 23 - Final pages ready for peer marking
* April 28 - Peer marking completed. Use the template at http://cs.ubc.ca/~poole/cs522/2018/project_eval.py

===Marking Scheme===
Here is a tentative marking scheme. This is subject to change. Feel free to add questions, and edit the questions if they do not make sense.

On a scale of 1 to 5, where 1 means "strongly disagree" and 5 means "strongly agree" please rate and comment on the following:
* The topic is relevant for the course.
* The writing is clear and the English is good.
* The page is written at an appropriate level for CPSC 522 students (where the students have diverse backgrounds).
* The formalism (definitions, mathematics) was well chosen to make the page easier to understand.
* The abstract is a concise and clear summary.
* There were appropriate (original) examples that helped make the topic clear.
* There was appropriate use of (pseudo-) code.
* It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic).
* It is correct.
* It was neither too short nor too long for the topic.
* It was an appropriate unit for a page (it shouldn't be split into different topics or merged with another page).
* It links to appropriate other pages in the wiki.
* The references and links to external pages are well chosen.
* I would recommend this page to someone who wanted to find out about the topic.
* This page should be highlighted as an exemplary page for others to emulate.

If I was grading it out of 20, I would give it:

Thread:Course talk:CPSC522/SLAM And Sensor Quality/Critique (2)

2018-04-23T06:56:53Z

AINAZHAJIMORADLOU: New thread: Critique

Overall, It's a good written page and the topic is interesting. However, I have some comments that might be useful:

1. There are some typos and grammatical errors in the page (e.g. based off, an simulated robot, etc.).

2. Although the problem is clear, it's still not clear why decreasing noise like nearly perfect sensors result in worse localization which then leads to robot being lost.

3. It would've been a good idea to write a conclusion/discussion section that summarizes the mentioned experiments and states the final conclusion on such systems.

---------------------------------------------------------------------------------------------------
Marking scheme:
* The topic is relevant for the course. 5
* The writing is clear and the English is good. 4
* The page is written at an appropriate level for CPSC 522 students (where the students have diverse backgrounds). 5
* The formalism (definitions, mathematics) was well chosen to make the page easier to understand. N/A
* The abstract is a concise and clear summary. 4
* There were appropriate (original) examples that helped make the topic clear. 5
* There was appropriate use of (pseudo-) code. 2
* It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic). N/A
* It is correct. 5
* It was neither too short nor too long for the topic. 5
* It was an appropriate unit for a page (it shouldn't be split into different topics or merged with another page). 5
* It links to appropriate other pages in the wiki. 3
* The references and links to external pages are well chosen. 4
* I would recommend this page to someone who wanted to find out about the topic. 4
* This page should be highlighted as an exemplary page for others to emulate. 4
If I was grading it out of 20, I would give it: 17

Thread:Course talk:CPSC522/Experiments with Reinforcement Learning/Critique 3

2018-04-23T04:02:07Z

AINAZHAJIMORADLOU: New thread: Critique 3

The page looks good! It has a good coverage and the explanations are thorough. I didn't actually find anything to critique except the fact that the page is incomplete and you can talk more about the results of the things you tried. Maybe talking a little more about frameworks/implementation details or challenges would be useful.

---------------------------------------------------------------------------------------------------
Marking scheme:
* The topic is relevant for the course. 5
* The writing is clear and the English is good. 5
* The page is written at an appropriate level for CPSC 522 students (where the students have diverse backgrounds). 5
* The formalism (definitions, mathematics) was well chosen to make the page easier to understand. 4
* The abstract is a concise and clear summary. 4
* There were appropriate (original) examples that helped make the topic clear. 4
* There was appropriate use of (pseudo-) code. N/A
* It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic). 3
* It is correct. 5
* It was neither too short nor too long for the topic. 5
* It was an appropriate unit for a page (it shouldn't be split into different topics or merged with another page). 5
* It links to appropriate other pages in the wiki. 2
* The references and links to external pages are well chosen. N/A
* I would recommend this page to someone who wanted to find out about the topic. 4
* This page should be highlighted as an exemplary page for others to emulate. 4
If I was grading it out of 20, I would give it: 18

Thread:Course talk:CPSC522/An evaluation on selecting and applying Recommendation Methods/Critique

2018-04-23T04:01:27Z

AINAZHAJIMORADLOU:

Hi guys,

Overal, it's a thorough survey on different methods of filtering. I have some comments that may be useful to you though:

1. There are some grammatical errors/typos such as "based off", "Be base our implementation based off the description of both methods", etc.

2. You might want to write references in [1] format instead of superscript in the original context. (e.g. in [1], they focus on ...)

3. It would be nice to have some quantitative results as well as qualitative results like using tables to report accuracy on some subset of dataset for all proposed algorithms and comparing them.

---------------------------------------------------------------------------------------------------
Marking scheme:
* The topic is relevant for the course. 5
* The writing is clear and the English is good. 4
* The page is written at an appropriate level for CPSC 522 students (where the students have diverse backgrounds). 5
* The formalism (definitions, mathematics) was well chosen to make the page easier to understand. 4
* The abstract is a concise and clear summary. 4
* There were appropriate (original) examples that helped make the topic clear. 4
* There was appropriate use of (pseudo-) code. 3
* It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic). N/A
* It is correct. 5
* It was neither too short nor too long for the topic. 5
* It was an appropriate unit for a page (it shouldn't be split into different topics or merged with another page). 5
* It links to appropriate other pages in the wiki. 3
* The references and links to external pages are well chosen. 4
* I would recommend this page to someone who wanted to find out about the topic. 4
* This page should be highlighted as an exemplary page for others to emulate. 4
If I was grading it out of 20, I would give it: 17

Thread:Course talk:CPSC522/An evaluation on selecting and applying Recommendation Methods/Critique

2018-04-23T03:45:20Z

AINAZHAJIMORADLOU:

Hi guys,

Overal, it's a thorough survey on different methods of filtering. I have some comments that may be useful to you though:

1. There are some grammatical errors/typos such as "based off", "Be base our implementation based off the description of both methods", etc.

2. You might want to write references in [1] format instead of superscript in the original context. (e.g. in [1], they focus on ...)

3. It would be nice to have some quantitative results as well as qualitative results like using tables to report accuracy on some subset of dataset for all proposed algorithms and comparing them.

---------------------------------------------------------------------------------------------------
Marking scheme:
* The topic is relevant for the course. 5
* The writing is clear and the English is good. 4
* The page is written at an appropriate level for CPSC 522 students (where the students have diverse backgrounds). 5
* The formalism (definitions, mathematics) was well chosen to make the page easier to understand. 4
* The abstract is a concise and clear summary. 4
* There were appropriate (original) examples that helped make the topic clear. 4
* There was appropriate use of (pseudo-) code. 3
* It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic). N/A
* It is correct. 5
* It was neither too short nor too long for the topic. 3 (It's a little short so far, but it seems obvious you intend to expand it a bit before the final version)
* It was an appropriate unit for a page (it shouldn't be split into different topics or merged with another page). 5
* It links to appropriate other pages in the wiki. N/A
* The references and links to external pages are well chosen. N/A
* I would recommend this page to someone who wanted to find out about the topic. 4
* This page should be highlighted as an exemplary page for others to emulate. 4
If I was grading it out of 20, I would give it: 17

Thread:Course talk:CPSC522/An evaluation on selecting and applying Recommendation Methods/Critique

2018-04-23T03:44:54Z

AINAZHAJIMORADLOU: New thread: Critique

Hi guys,
Overal, it's a thorough survey on different methods of filtering. I have some comments that may be useful to you though:
1. There are some grammatical errors/typos such as "based off", "Be base our implementation based off the description of both methods", etc.
2. You might want to write references in [1] format instead of superscript in the original context. (e.g. in [1], they focus on ...)
3. It would be nice to have some quantitative results as well as qualitative results like using tables to report accuracy on some subset of dataset for all proposed algorithms and comparing them.
---------------------------------------------------------------------------------------------------
Marking scheme:
* The topic is relevant for the course. 5
* The writing is clear and the English is good. 4
* The page is written at an appropriate level for CPSC 522 students (where the students have diverse backgrounds). 5
* The formalism (definitions, mathematics) was well chosen to make the page easier to understand. 4
* The abstract is a concise and clear summary. 4
* There were appropriate (original) examples that helped make the topic clear. 4
* There was appropriate use of (pseudo-) code. 3
* It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic). N/A
* It is correct. 5
* It was neither too short nor too long for the topic. 3 (It's a little short so far, but it seems obvious you intend to expand it a bit before the final version)
* It was an appropriate unit for a page (it shouldn't be split into different topics or merged with another page). 5
* It links to appropriate other pages in the wiki. N/A
* The references and links to external pages are well chosen. N/A
* I would recommend this page to someone who wanted to find out about the topic. 4
* This page should be highlighted as an exemplary page for others to emulate. 4
If I was grading it out of 20, I would give it: 17

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-23T03:27:37Z

AINAZHAJIMORADLOU: /* Approach */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|300px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

[[File:Motion_demo.gif|300px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]]
Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity and the spent time, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Demo motion2.gif|300px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]
Figure 4 shows an example of the results obtained by the baseline. In this case, the velocities along each axis are increased to the same extent. Therefore, the robot moves in the y = x direction. However, this is not optimal as the robot's direction changes every now and then. Depending on the direction, the velocities should be amplified accordingly. To solve this, we can simply find the angle between current position of the robot and the desired direction which is the goal. Cosine and Sine of this angle will be the multipliers of the velocities in x and y axes. The updated results are shown in figure 5. The direction of the user in this figure is at point (1, 0).

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|200px|thumb|left|A simulated differential drive robot using the RobotPy package.]]
The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.

To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.
Besides, speaking in terms of model, we can smooth the obtained parameters of the state by using moving average instead of finding a desired velocity in the specified margin. To further extend the project we should focus on adapting the model to more complex simulation environments as the one shown in figure 6.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-23T03:26:15Z

AINAZHAJIMORADLOU: /* Simulated Environment */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|300px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

[[File:Motion_demo.gif|300px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]]
Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Demo motion2.gif|300px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]
Figure 4 shows an example of the results obtained by the baseline. In this case, the velocities along each axis are increased to the same extent. Therefore, the robot moves in the y = x direction. However, this is not optimal as the robot's direction changes every now and then. Depending on the direction, the velocities should be amplified accordingly. To solve this, we can simply find the angle between current position of the robot and the desired direction which is the goal. Cosine and Sine of this angle will be the multipliers of the velocities in x and y axes. The updated results are shown in figure 5. The direction of the user in this figure is at point (1, 0).

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|200px|thumb|left|A simulated differential drive robot using the RobotPy package.]]
The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.

To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.
Besides, speaking in terms of model, we can smooth the obtained parameters of the state by using moving average instead of finding a desired velocity in the specified margin. To further extend the project we should focus on adapting the model to more complex simulation environments as the one shown in figure 6.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T08:21:43Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|300px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

[[File:Motion_demo.gif|300px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]]
Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Demo motion2.gif|300px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]
Figure 4 shows an example of the results obtained by the baseline. In this case, the velocities along each axis are increased to the same extent. Therefore, the robot moves in the y = x direction. However, this is not optimal as the robot's direction changes every now and then. Depending on the direction, the velocities should be amplified accordingly. To solve this, we can simply find the angle between current position of the robot and the desired direction which is the goal. Cosine and Sine of this angle will be the multipliers of the velocities in x and y axes. The updated results are shown in figure 5. The direction of the user in this figure is at point (1, 0).

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|200px|thumb|left|A simulated differential drive robot using the RobotPy package.]]
The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.

To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.
Besides, speaking in terms of model, we can smooth the obtained parameters of the state by using moving average instead of finding a desired velocity in the specified margin. To further extend the project we should focus on adapting the model to more complex simulation environments as the one shown in figure 6.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T08:17:47Z

AINAZHAJIMORADLOU: /* Future Work */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|280px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|280px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]] [[File:Demo motion2.gif|280px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]
Figure 4 shows an example of the results obtained by the baseline. In this case, the velocities along each axis are increased to the same extent. Therefore, the robot moves in the y = x direction. However, this is not optimal as the robot's direction changes every now and then. Depending on the direction, the velocities should be amplified accordingly. To solve this, we can simply find the angle between current position of the robot and the desired direction which is the goal. Cosine and Sine of this angle will be the multipliers of the velocities in x and y axes. The updated results are shown in figure 5. The direction of the user in this figure is at point (1, 0).

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|100px|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.

To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

Besides, speaking in terms of model, we can smooth the obtained parameters of the state by using moving average instead of finding a desired velocity in the specified margin. To further extend the project we should focus on adapting the model to more complex simulation environments as the one shown in figure 6.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T08:16:37Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|280px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|280px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]] [[File:Demo motion2.gif|280px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]
Figure 4 shows an example of the results obtained by the baseline. In this case, the velocities along each axis are increased to the same extent. Therefore, the robot moves in the y = x direction. However, this is not optimal as the robot's direction changes every now and then. Depending on the direction, the velocities should be amplified accordingly. To solve this, we can simply find the angle between current position of the robot and the desired direction which is the goal. Cosine and Sine of this angle will be the multipliers of the velocities in x and y axes. The updated results are shown in figure 5. The direction of the user in this figure is at point (1, 0).

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|200px|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.

To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

Besides, speaking in terms of model, we can smooth the obtained parameters of the state by using moving average instead of finding a desired velocity in the specified margin. To further extend the project we should focus on adapting the model to more complex simulation environments as the one shown in figure 6.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T08:15:01Z

AINAZHAJIMORADLOU: Undo revision 518142 by AINAZHAJIMORADLOU (talk)

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|300px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|250px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]] [[File:Demo motion2.gif|250px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]
Figure 4 shows an example of the results obtained by the baseline. In this case, the velocities along each axis are increased to the same extent. Therefore, the robot moves in the y = x direction. However, this is not optimal as the robot's direction changes every now and then. Depending on the direction, the velocities should be amplified accordingly. To solve this, we can simply find the angle between current position of the robot and the desired direction which is the goal. Cosine and Sine of this angle will be the multipliers of the velocities in x and y axes. The updated results are shown in figure 5. The direction of the user in this figure is at point (1, 0).

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|200px|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.

To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

Besides, speaking in terms of model, we can smooth the obtained parameters of the state by using moving average instead of finding a desired velocity in the specified margin. To further extend the project we should focus on adapting the model to more complex simulation environments as the one shown in figure 6.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T08:13:47Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|300px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|250px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]] [[File:Demo motion2.gif|250px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.
To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T08:12:19Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|300px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|250px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]] [[File:Demo motion2.gif|250px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]
Figure 4 shows an example of the results obtained by the baseline. In this case, the velocities along each axis are increased to the same extent. Therefore, the robot moves in the y = x direction. However, this is not optimal as the robot's direction changes every now and then. Depending on the direction, the velocities should be amplified accordingly. To solve this, we can simply find the angle between current position of the robot and the desired direction which is the goal. Cosine and Sine of this angle will be the multipliers of the velocities in x and y axes. The updated results are shown in figure 5. The direction of the user in this figure is at point (1, 0).

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|200px|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.

To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

Besides, speaking in terms of model, we can smooth the obtained parameters of the state by using moving average instead of finding a desired velocity in the specified margin. To further extend the project we should focus on adapting the model to more complex simulation environments as the one shown in figure 6.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T05:26:07Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|300px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|300px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]] [[File:Demo motion2.gif|300px|thumb|''Figure 5.'' Simple robot motion with different velocities along each axis.]]

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.
To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

File:Motion demo.gif

2018-04-19T05:22:45Z

AINAZHAJIMORADLOU: AINAZHAJIMORADLOU uploaded a new version of "File:Motion demo.gif"

=={{int:filedesc}}==
{{Information
|description={{en|1=A simple robot motion based on the proposed baseline.}}
|date=2018-04-18 22:02:34
|source={{own}}
|author=[[User:AINAZHAJIMORADLOU|AINAZHAJIMORADLOU]]
|permission=
|other_versions=
}}

=={{int:license-header}}==
{{self|cc-by-sa-3.0}}

[[Category:Uploaded with UploadWizard]]

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T05:20:56Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|380px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|380px|thumb|left|''Figure 4.'' A simple robot motion based on the proposed baseline.]]
[[File:Demo motion2.gif|380px|thumb|left|''Figure 5.'' Simple robot motion with different velocities along each axis.]]

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.
To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

File:Demo motion2.gif

2018-04-19T05:20:08Z

AINAZHAJIMORADLOU: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Simple robot motion with different velocities along each axis.}}
|date=2018-04-18 22:19:11
|source={{own}}
|author=[[User:AINAZHAJIMORADLOU|AINAZHAJIMORADLOU]]
|permission=
|other_versions=
}}

=={{int:license-header}}==
{{self|cc-by-sa-3.0}}

[[Category:Uploaded with UploadWizard]]

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T05:16:22Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|380px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|380px|thumb|''Figure 4.'' A simple robot motion based on the proposed baseline.]]

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.
To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

File:Motion demo.gif

2018-04-19T05:15:30Z

AINAZHAJIMORADLOU: AINAZHAJIMORADLOU uploaded a new version of "File:Motion demo.gif"

File:Motion demo.gif

2018-04-19T05:14:32Z

AINAZHAJIMORADLOU: AINAZHAJIMORADLOU uploaded a new version of "File:Motion demo.gif"

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T05:13:46Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|380px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' Magnitude of velocity of the user at each time step.]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===
[[File:Motion_demo.gif|thumb|A simple robot motion based on the proposed baseline.]]

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.
To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

File:Motion demo.gif

2018-04-19T05:10:22Z

AINAZHAJIMORADLOU: AINAZHAJIMORADLOU uploaded a new version of "File:Motion demo.gif"

File:Motion demo.gif

2018-04-19T05:07:56Z

AINAZHAJIMORADLOU: AINAZHAJIMORADLOU uploaded a new version of "File:Motion demo.gif"

File:Motion demo.gif

2018-04-19T05:03:06Z

AINAZHAJIMORADLOU: User created page with UploadWizard

Course:CPSC522/Learning User Preferences of Motion Control

2018-04-19T04:35:18Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Title ==
The goal of this project is to add intervention to a power wheelchair system so that when the user expresses frustration due to limited joystick control abilities, the system can adjust the control to match the users preference.

Principal Author: Ainaz Hajimoradlou, Jocelyn Minns 

== Content ==

=== Problem ===
[[File:PWCPartsDiagram.jpg|250px||thumb|''Figure 1.'' Design of a Power Wheelchair. Image source from usmedicalsupplies.com]]

Modern power wheelchairs are an essential tool to many who are mobility challenged. However, while this gives freedom to some who would otherwise be restricted in their day to day life, other users are still limited from safely operating these large, heavy and powerful machines. Users that experience motor and/or cognitive impairments may be be unable to operate a power wheelchair to the accuracy that is required.
Most common power wheelchairs are operated using a joystick controller to steer the motors. If the user is unable to perform the small movements for persuasion control and the large movements to achieve reasonable speed, then they could become frustrated and may compromise their own safety. The goal of this project is to add intervention to the system so that when the user expresses frustration with the control of the power wheelchair, the system can adjust to match the users preference.

=== Simulated Environment ===
[[File:Test-drive-holonomic.gif|380px||thumb|left|''Figure 2.'' A simulated holonomic robot exploring the environment.]]

The most common form of a power wheelchair can be modelled as a differential drive robot. Meaning that the robot has two main wheels attached to the sides of the robot each with its own motor. A wheelchair also contains four caster wheels at the front and back to ensure stability and balance. The caster wheels generally do not effect the motion of the chair since they can rotate freely and are not attached to any motor. Since each of the two main wheel are attached to its own motor, they can rotate in opposite directions or at different velocities allowing the user to turn or even spin in place. This model proposes its own set of challenges in simulation. Accurately mapping the linear and rotational velocities given the user input from the joystick control can be a large problem on its own.

To test our initial approach, it is desirable to start with a simpler model than the one described above. Using a holonomic robot design lifts some of the resections of the differential drive design allowing us to easily simulate the movement of the robot. With this design, the robot is free to move in any direction in the x-y plane. We can then focus on the linear velocity only and adapt to the users preferences accordingly.

For our simulation, we are not able to use real power wheelchair users to provide feedback for our system. Instead we simulate users such that each user will have a set level of ability to use the joystick controls and a desired speed that they wish to go. The desired speed remains unknown to the system, the only feedback that the user gives is a verbal description of the speed as as too fast or too slow. The joystick controls are fed to the system at 30 Hz, however the user is unable to provide feedback at that rate so there is some delay to the users commands based on the accurate movement of the chair.

=== Approach ===

[[File:Motion control plot.png|380px||thumb|''Figure 3.'' motion control plot]]
The first models we considered were Markov models such as [https://en.wikipedia.org/wiki/Markov_chain Markov chains], [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and Continuous Markov process. Since, obtaining the parameters of each state such as velocity and position depends on previous states. However, we encountered a problem when fitting data with these models due to the nature of the proposed problem. We have to get the feedback from the user in form of verbal complaint, but these models do not support having such inputs. Therefore, we decided to go with a simple version of a baseline model.

Each state in the model specifies current velocity, position and the direction the user is going with joystick controllers. A desired linear velocity exists which is specified by user as the input to the model. So, based on this linear speed, feedbacks are divided into three categories: fast, good and slow. The model's approach is to start with increasing the velocity until the feedback from the user states that the speed is too fast. The point where this feedback is achieved, high margin of the speed is obtained. Low margin is the previous state's velocity. Based on these margins, the desired speed of the user is obtained by a simple binary search. When the desired speed is achieved, user will give a feedback ("good speed") and the velocity will remain constant until the user's direction changes. So at each time step, based on current velocity, the position of the user is updated in the plot. This process will repeat until the user stops or reaches the desired speed. The magnitude of velocity at each time step is plotted in figure 3.

=== Results ===

=== Future Work ===
[[File:Test-drive-nonholonomic.gif|thumb|left|A simulated differential drive robot using the RobotPy package.]]

The two main focuses for future work is to improve the robot design of the power wheelchair and to improve the simulated user.
Using a predesigned robot simulator such as RobotPy, we are able to simulate a differential drive robot. However, the mapping of the joystick controller to the movement is highly inaccurate to a real wheelchair system. Power wheelchairs inherently apply some mapping function from the control to the motors to provide the user with safer control. Examples of this is the decreased velocity when backing up or the decreased rotational velocity when spinning in place. To build a mapping of the control to the motors is a non trivial job, but would be necessary to use a more accurate model. Once the model was in place, we would be able to adjust the control to accommodate the users preference for both the linear and rotational velocities.
To improve the simulated user, we would add noise to the users inputs/outputs. The user perception of the velocity would have some variation as well as the users ability to use the joystick control. The user would also want to adjust their desired speed given different environments or different obstacles.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

File:Motion control plot.png

2018-04-19T04:22:01Z

AINAZHAJIMORADLOU: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=motion control plot}}
|date=2018-04-18 21:21:25
|source={{own}}
|author=[[User:AINAZHAJIMORADLOU|AINAZHAJIMORADLOU]]
|permission=
|other_versions=
}}

=={{int:license-header}}==
{{self|cc-by-sa-3.0}}

[[Category:Uploaded with UploadWizard]]

Course:CPSC522/StudentPresentations2018

2018-04-17T04:09:38Z

AINAZHAJIMORADLOU:

==CPSC 522 - Project Presentation Schedule 2018-04-17 ==
The project presentations will be on 2018-04-17 at 10:00 in room 146. Please add you name either before or after the break. You are only allowed to add your name to one of the times marked with #
# Borna
# Vanessa
# Fabian
# Wenyi
# May
# David
# Ekta
# Jocelyn, Ainaz
#
# Break
# Surbhi
#
#
#
#
#
#
#
#

==CPSC 522 - January to April 2018 Student Presentation Schedule==
Please sign up for a date you want to present. There is a maximum of three students per slot. (Hopefully most slots will end up with three presenters). The three students '''must coordinate''' to present the two papers in 60 minutes. All three students must present. The two papers are related. It is suggested that one student gives 20 minutes background, and the other students each present 20 minutes for one of the papers. But the format is up to the presenters.

The schedule of which papers are presented each day is at http://www.cs.ubc.ca/~poole/cs522/2018/schedule.html

==Dates==
* Jan 16 - Everyone!
* Jan 23 -
* Jan 30 -
* Feb 8 - David Johnson, May Young
* Feb 15 - Kevin Dsouza, Bronson Bouchard
* Mar 1 - Kumseok Jung, Julin Song, Ekta Aggarwal
* Mar 8 - Fabian Ruffy, Alistair Wick, Gudbrand Tandberg
* Mar 15 - Borna Ghotbi, Vanessa Putnam
* Mar 22 - Amin Aghaee, Carl Kwan, Surbhi Palande
* Mar 29 -
* Apr 3 - Wenyi Wang, Ainaz Hajimoradlou, Jocelyn Minns

Course:CPSC522/Deep Reinforcement Learning

2018-03-23T20:25:50Z

AINAZHAJIMORADLOU: /* Abstract */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
Deep learning models such as [https://en.wikipedia.org/wiki/Artificial_neural_network neural networks] that are used in [https://en.wikipedia.org/wiki/Reinforcement_learning reinforcement learning] to learn control policies directly from high dimensional data are part of deep reinforcement learning. In other words, deep reinforcement learning is a combination of reinforcement learning and deep learning techniques.

Principal Author: Ainaz Hajimoradlou 
Collaborators:

== Abstract ==
This page gives a short review of two papers in deep reinforcement learning. The first paper discusses a new approach for integrating deep learning techniques into reinforcement learning problems. The model is experimented on 7 different Atari games and is able to achieve higher scores in comparison to state of the art models at that time. The second paper expands this approach by 6 different techniques such as different architectures and sampling techniques on 57 Atari games. The model is able to achieve better scores compared to the previous approach.
===Builds on===
This page builds on general concepts such as [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] and [[Course:CPSC522/Neural_Network|Neural Networks]]. The [[Course:CPSC522/Convolutional_Neural_Networks|convolutional neural networks]] along with [[Course:CPSC522/Reinforcement_Learning_with_Function_approximation|function approximators]] are used to model games like [[Course:CPSC522/Deep_Neural_Network|Alpha go]] using reinforcement learning techniques.

===Related Pages===
Games like [[Course:CPSC522/Deep_Neural_Network|Alpha go]] are some examples of applications of deep reinforcement learning. These models are usually based on non-linear [[Course:CPSC522/Reinforcement_Learning_with_Function_approximation|function approximators]] such as [[Course:CPSC522/Convolutional_Neural_Networks|convolutional neural networks]]. Moreover, the essence of deep reinforcement learning algorithms is dependent on [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]].

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.

====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]
Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

=== Discussion ===
The first paper introduces a new approach to deep reinforcement learning by a non-linear function approximator. Although, the chances of getting a deep network to work with reinforcement learning algorithms is very low, the paper was able to achieve not only reasonably good results but higher scores compared to the state of the art approaches which was a big breakthrough in this area. On the other hand, the second paper is actually just an integration method of different existing extensions to the proposed algorithm in the first paper. Each of these extensions have been used to improve one of the limitations of deep Q-learning. Therefore, having a model composed of all these extensions has resulted in improvement of the original model.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-23T20:19:56Z

AINAZHAJIMORADLOU: /* Deep Reinforcement Learning */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
Deep learning models such as [https://en.wikipedia.org/wiki/Artificial_neural_network neural networks] that are used in [https://en.wikipedia.org/wiki/Reinforcement_learning reinforcement learning] to learn control policies directly from high dimensional data are part of deep reinforcement learning. In other words, deep reinforcement learning is a combination of reinforcement learning and deep learning techniques.

Principal Author: Ainaz Hajimoradlou 
Collaborators:

== Abstract ==
This page gives a short review of two papers in deep reinforcement learning. The first paper discusses a new approach for integrating deep learning techniques into reinforcement learning problems. The model is experimented on 7 different Atari games and is able to achieve higher scores in comparison to state of the art models at that time. The second paper expands this approach by 6 different techniques such as different architectures and sampling techniques on 57 Atari games. The model is able to achieve better scores compared to the previous approach.
===Builds on===
This page builds on general concepts such as [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] and [[Course:CPSC522/Neural_Network|Neural Networks]]. The [[Course:CPSC522/Convolutional_Neural_Networks|convolutional neural networks]] along with [[Course:CPSC522/Reinforcement_Learning_with_Function_approximation|function approximators]] are used to model games like [[Course:CPSC522/Deep_Neural_Network|Alpha go]] using reinforcement learning techniques.

===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.

====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]
Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

=== Discussion ===
The first paper introduces a new approach to deep reinforcement learning by a non-linear function approximator. Although, the chances of getting a deep network to work with reinforcement learning algorithms is very low, the paper was able to achieve not only reasonably good results but higher scores compared to the state of the art approaches which was a big breakthrough in this area. On the other hand, the second paper is actually just an integration method of different existing extensions to the proposed algorithm in the first paper. Each of these extensions have been used to improve one of the limitations of deep Q-learning. Therefore, having a model composed of all these extensions has resulted in improvement of the original model.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-20T19:35:58Z

AINAZHAJIMORADLOU: /* Builds on */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
Deep learning techniques such as [https://en.wikipedia.org/wiki/Artificial_neural_network neural networks] that are used in [https://en.wikipedia.org/wiki/Reinforcement_learning reinforcement learning] to learn control policies directly from high dimensional data are called deep reinforcement learning.

Principal Author: Ainaz Hajimoradlou 
Collaborators:

== Abstract ==
This page gives a short review of two papers in deep reinforcement learning. The first paper discusses a new approach for integrating deep learning techniques into reinforcement learning problems. The model is experimented on 7 different Atari games and is able to achieve higher scores in comparison to state of the art models at that time. The second paper expands this approach by 6 different techniques such as different architectures and sampling techniques on 57 Atari games. The model is able to achieve better scores compared to the previous approach.
===Builds on===
This page builds on general concepts such as [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] and [[Course:CPSC522/Neural_Network|Neural Networks]]. The [[Course:CPSC522/Convolutional_Neural_Networks|convolutional neural networks]] along with [[Course:CPSC522/Reinforcement_Learning_with_Function_approximation|function approximators]] are used to model games like [[Course:CPSC522/Deep_Neural_Network|Alpha go]] using reinforcement learning techniques.

===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.

====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]
Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

=== Discussion ===
The first paper introduces a new approach to deep reinforcement learning by a non-linear function approximator. Although, the chances of getting a deep network to work with reinforcement learning algorithms is very low, the paper was able to achieve not only reasonably good results but higher scores compared to the state of the art approaches which was a big breakthrough in this area. On the other hand, the second paper is actually just an integration method of different existing extensions to the proposed algorithm in the first paper. Each of these extensions have been used to improve one of the limitations of deep Q-learning. Therefore, having a model composed of all these extensions has resulted in improvement of the original model.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-20T19:35:37Z

AINAZHAJIMORADLOU: /* Abstract */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
Deep learning techniques such as [https://en.wikipedia.org/wiki/Artificial_neural_network neural networks] that are used in [https://en.wikipedia.org/wiki/Reinforcement_learning reinforcement learning] to learn control policies directly from high dimensional data are called deep reinforcement learning.

Principal Author: Ainaz Hajimoradlou 
Collaborators:

== Abstract ==
This page gives a short review of two papers in deep reinforcement learning. The first paper discusses a new approach for integrating deep learning techniques into reinforcement learning problems. The model is experimented on 7 different Atari games and is able to achieve higher scores in comparison to state of the art models at that time. The second paper expands this approach by 6 different techniques such as different architectures and sampling techniques on 57 Atari games. The model is able to achieve better scores compared to the previous approach.
===Builds on===
This page builds on general concepts such as [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] and [[Course:CPSC522/Neural_Network|Neural Networks]]. The [[Course:CPSC522/Convolutional_Neural_Networks|convolutional neural networks]] along with [[Course:CPSC522/Reinforcement_Learning_with_Function_approximation|function approximators]] are used to model games like [[Course:CPSC522/Deep_Neural_Network|Alpha go]] using reinforcement learning techniques.
,===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.

====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]
Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

=== Discussion ===
The first paper introduces a new approach to deep reinforcement learning by a non-linear function approximator. Although, the chances of getting a deep network to work with reinforcement learning algorithms is very low, the paper was able to achieve not only reasonably good results but higher scores compared to the state of the art approaches which was a big breakthrough in this area. On the other hand, the second paper is actually just an integration method of different existing extensions to the proposed algorithm in the first paper. Each of these extensions have been used to improve one of the limitations of deep Q-learning. Therefore, having a model composed of all these extensions has resulted in improvement of the original model.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T21:26:38Z

AINAZHAJIMORADLOU: /* Abstract */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
Deep learning techniques such as [https://en.wikipedia.org/wiki/Artificial_neural_network neural networks] that are used in [https://en.wikipedia.org/wiki/Reinforcement_learning reinforcement learning] to learn control policies directly from high dimensional data are called deep reinforcement learning.

Principal Author: Ainaz Hajimoradlou 
Collaborators:

== Abstract ==
This page gives a short review of two papers in deep reinforcement learning. The first paper discusses a new approach for integrating deep learning techniques into reinforcement learning problems. The model is experimented on 7 different Atari games and is able to achieve higher scores in comparison to state of the art models at that time. The second paper expands this approach by 6 different techniques such as different architectures and sampling techniques on 57 Atari games. The model is able to achieve better scores compared to the previous approach.
===Builds on===
This page builds on general concepts of deep learning, reinforcement learning and neural network.
===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.

====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]
Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

=== Discussion ===
The first paper introduces a new approach to deep reinforcement learning by a non-linear function approximator. Although, the chances of getting a deep network to work with reinforcement learning algorithms is very low, the paper was able to achieve not only reasonably good results but higher scores compared to the state of the art approaches which was a big breakthrough in this area. On the other hand, the second paper is actually just an integration method of different existing extensions to the proposed algorithm in the first paper. Each of these extensions have been used to improve one of the limitations of deep Q-learning. Therefore, having a model composed of all these extensions has resulted in improvement of the original model.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T21:17:28Z

AINAZHAJIMORADLOU: /* Deep Reinforcement Learning */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
Deep learning techniques such as [https://en.wikipedia.org/wiki/Artificial_neural_network neural networks] that are used in [https://en.wikipedia.org/wiki/Reinforcement_learning reinforcement learning] to learn control policies directly from high dimensional data are called deep reinforcement learning.

Principal Author: Ainaz Hajimoradlou 
Collaborators:

== Abstract ==
This should be a brief summary that tells us what is covered in this page.
===Builds on===
Put links to the more general categories that this builds on. These links should all be in sentences that make sense without following the links. You can only rely on technical knowledge that is in these links (and their transitive closure). There is no need to put the transitive closure of the links.
===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.

====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]
Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

=== Discussion ===
The first paper introduces a new approach to deep reinforcement learning by a non-linear function approximator. Although, the chances of getting a deep network to work with reinforcement learning algorithms is very low, the paper was able to achieve not only reasonably good results but higher scores compared to the state of the art approaches which was a big breakthrough in this area. On the other hand, the second paper is actually just an integration method of different existing extensions to the proposed algorithm in the first paper. Each of these extensions have been used to improve one of the limitations of deep Q-learning. Therefore, having a model composed of all these extensions has resulted in improvement of the original model.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T21:06:38Z

AINAZHAJIMORADLOU: /* To Add */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
One sentence summary

Principal Author: Ainaz Hajimoradlou 
Collaborators:
== Abstract ==
This should be a brief summary that tells us what is covered in this page.
===Builds on===
Put links to the more general categories that this builds on. These links should all be in sentences that make sense without following the links. You can only rely on technical knowledge that is in these links (and their transitive closure). There is no need to put the transitive closure of the links.
===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.

====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]
Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

=== Discussion ===
The first paper introduces a new approach to deep reinforcement learning by a non-linear function approximator. Although, the chances of getting a deep network to work with reinforcement learning algorithms is very low, the paper was able to achieve not only reasonably good results but higher scores compared to the state of the art approaches which was a big breakthrough in this area. On the other hand, the second paper is actually just an integration method of different existing extensions to the proposed algorithm in the first paper. Each of these extensions have been used to improve one of the limitations of deep Q-learning. Therefore, having a model composed of all these extensions has resulted in improvement of the original model.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T21:06:19Z

AINAZHAJIMORADLOU: /* Annotated Bibliography */

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T21:05:59Z

AINAZHAJIMORADLOU: /* Discussion */

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T21:05:31Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
One sentence summary

Principal Author: Ainaz Hajimoradlou 
Collaborators:
== Abstract ==
This should be a brief summary that tells us what is covered in this page.
===Builds on===
Put links to the more general categories that this builds on. These links should all be in sentences that make sense without following the links. You can only rely on technical knowledge that is in these links (and their transitive closure). There is no need to put the transitive closure of the links.
===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.

====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]
Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

=== Discussion ===
The first paper introduces a new approach to deep reinforcement learning by a non-linear function approximator. Although, the chances of getting a deep network to work with reinforcement learning algorithms is very low, the paper was able to achieve not only reasonably good results but higher scores compared to the state of the art approaches which was a big breakthrough in this area. On the other hand, the second paper is actually just an integration method of different existing extensions to the proposed algorithm in the first paper. Each of these extensions have been used to improve one of the limitations of deep Q-learning. Therefore, having a model composed of all these extensions has resulted in improvement of the original model.

== Discussion ==

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

[https://arxiv.org/pdf/1312.5602.pdf V. Minh, et al., Playing Atari with Deep Reinforcement Learning]

[https://arxiv.org/pdf/1710.02298.pdf M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning]

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T20:47:10Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
One sentence summary

Principal Author: Ainaz Hajimoradlou 
Collaborators:
== Abstract ==
This should be a brief summary that tells us what is covered in this page.
===Builds on===
Put links to the more general categories that this builds on. These links should all be in sentences that make sense without following the links. You can only rely on technical knowledge that is in these links (and their transitive closure). There is no need to put the transitive closure of the links.
===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Paper I, Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Paper ||, Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.
====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games. Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning</ref>.]]

== Discussion ==

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

[https://arxiv.org/pdf/1312.5602.pdf V. Minh, et al., Playing Atari with Deep Reinforcement Learning]

[https://arxiv.org/pdf/1710.02298.pdf M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning]

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T20:44:51Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
One sentence summary

Principal Author: Ainaz Hajimoradlou 
Collaborators:
== Abstract ==
This should be a brief summary that tells us what is covered in this page.
===Builds on===
Put links to the more general categories that this builds on. These links should all be in sentences that make sense without following the links. You can only rely on technical knowledge that is in these links (and their transitive closure). There is no need to put the transitive closure of the links.
===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.
====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games. Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.
[[File:Rainbow DQN.png|1200px||thumb|'''Figure 2.''' First row shows the number of games where each agent was able to achieve at least a fraction of human performance as a function of time. The bottom row compares performance of rainbow to the models where some component is removed from the original model<ref name="paper2">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>.]]

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

[https://arxiv.org/pdf/1312.5602.pdf V. Minh, et al., Playing Atari with Deep Reinforcement Learning]

[https://arxiv.org/pdf/1710.02298.pdf M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning]

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

File:Rainbow DQN.png

2018-03-19T20:38:01Z

AINAZHAJIMORADLOU: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Deep Q network}}
|date=2018-03-19 13:36:18
|source=Rainbow: Combining Improvements in Deep Reinforcement Learning
|author=M. Hessel, et. al.
|permission=
|other_versions=
}}

=={{int:license-header}}==
{{subst:uwl}}

[[Category:Uploaded with UploadWizard]]

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T20:36:31Z

AINAZHAJIMORADLOU: /* Rainbow: Combining Improvements in Deep Reinforcement Learning */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
One sentence summary

Principal Author: Ainaz Hajimoradlou 
Collaborators:
== Abstract ==
This should be a brief summary that tells us what is covered in this page.
===Builds on===
Put links to the more general categories that this builds on. These links should all be in sentences that make sense without following the links. You can only rely on technical knowledge that is in these links (and their transitive closure). There is no need to put the transitive closure of the links.
===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning: DQN accumulates a single reward and then uses greedy action at the next step to bootstrap. An an alternative, forward-view multi-step targets<ref>Richard S Sutton, Learning to predict by the methods of temporal differences</ref> can be used for optimizing the parameters which can lead to faster learning with suitable <math>n</math>. Therefore, the reward function will be defined as follows.
:<math>
R_t^{(n)} \equiv \sum_{k=0}^{n-1} \gamma_t^{(k)}R_{t+k+1}
</math>
* Distributional RL: Instead of approximating the expected return, the distribution of returns can be estimated<ref>Bellemare, Dabney, and Munos, Distributional Reinforcement Learning with Quantile Regression</ref>. Therefore, the output of the network would be the distribution over each action.
* Noisy Nets: Exploration using <math>\epsilon</math>-greedy approaches is not suitable for situations where a lot of actions should be executed to collect the first reward. In these cases a model with a linear layer composed of a deterministic and noisy stream is proposed<ref>Fortunato et. al., Noisy Networks for Exploration</ref>. The model makes the network learn that it can ignore the noisy stream. The extent varies as the state space changes. This will allow state-conditional exploration with a form of self annealing. <math>\epsilon^b</math> and <math>\epsilon^w</math> are random variables and <math>\odot</math> is the element-wise multiplication.
:<math>
y = (b+Wx) + (b_{noisy}\odot\epsilon^b + (W_{noisy}\odot \epsilon^w)x)
</math>
The paper uses the integrated version of all above extensions as the original model. They combine a multi-step distributional loss with double Q-learning to choose the best action. They use prioritized experience replay to store the most frequent transitions in the memory. The network architecture is a dueling network which is adapted to use return distributions and all the linear layers are replaced with their equivalent noisy nets.
====Experiments====
The model is evaluated on 57 Atari games. The results are compared to human performance in all games. As the model is actually a combination of 6 other models, the number of hyper-parameters is large. Therefore, some tuning is needed for each component. The initial values are the values proposed by the original papers corresponding to each component. Then, the most sensitive ones are tuned using manual [https://en.wikipedia.org/wiki/Coordinate_descent coordinate descent]. The hyper parameters are the same across all games. Figure 2, top row, shows different plots for several agents, each plot represents the number of games the agent was able to achieve a given fraction of human performance. Bottom row shows the significance of each component in the integrated model by removing each component from the model and observing the performance.

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

[https://arxiv.org/pdf/1312.5602.pdf V. Minh, et al., Playing Atari with Deep Reinforcement Learning]

[https://arxiv.org/pdf/1710.02298.pdf M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning]

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-19T19:10:06Z

AINAZHAJIMORADLOU: /* Content */

[[Category:CPSC522]]
== Deep Reinforcement Learning ==
One sentence summary

Principal Author: Ainaz Hajimoradlou 
Collaborators:
== Abstract ==
This should be a brief summary that tells us what is covered in this page.
===Builds on===
Put links to the more general categories that this builds on. These links should all be in sentences that make sense without following the links. You can only rely on technical knowledge that is in these links (and their transitive closure). There is no need to put the transitive closure of the links.
===Related Pages===
This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

== Content ==
=== Playing Atari with Deep Reinforcement Learning ===
==== Introduction ====
Throughout past years, deep learning techniques have been widely applied to many vision and speech problems and they were able to improve the final results to large extents. However, these techniques are not very successful when applied to reinforcement learning problems due to variety of reasons:
* Most of the successful deep learning techniques require a great amount of hand labelled data for training but reinforcement learning algorithms are trained based on a scalar reward which is usually noisy, sparse and delayed. In other words, in order to train an RL algorithm the corresponding reward for each possible action should be received which can take a long time (e.g. thousands of time steps). This is quite challenging compared to the direct relation between targets and inputs in supervised learning.
* Machine learning and deep learning methods are mostly relied on data being IID. However, most of the data sequences in reinforcement learning are highly correlated.
* Deep methods are trained based on the assumption that training/testing dataset has an unknown stationary distribution. But in reinforcement learning, distribution of the data changes whenever the model encounters new behaviours in the environment.
In order to alleviate these problems, experience replay techniques are often used in RL problems. This is typically sampling randomly from the previous experience or transitions. As a result, the training distribution becomes smoother and easier to learn.

This paper proposes a deep reinforcement learning algorithm for 7 different Atari games. No prior knowledge is passed to the agent except the possible actions, reward, terminal signals and the video screen of the play which is available to human players as well.

==== Background ====
The agent interacts with the environment <math>\varepsilon</math> in a sequence of actions, observations and rewards. Action <math>a_t</math> can be chosen from a set of legal actions <math>\Alpha = \{1, ..., K\}</math>. After doing an action, the internal state of the emulator along with the game score is changed. This change is the reward <math>r_t</math> at time step <math>t</math>. The environment can be stochastic or deterministic. As the agent is only able to observe the raw pixels of the screen and not the whole state, the task is partially observable. Therefore, in order to understand the current situation a sequence of actions and observations (<math>x_1, a_1, x_2, a_2, ..., a_{t-1}, x_t</math>) should be considered. Each sequence is a state (<math>s_t</math>) at time <math>t</math>. States are distinct and have the [https://en.wikipedia.org/wiki/Markov_property Markov property]. Therefore, reinforcement learning techniques can be applied to this problem.

The goal is acting in a way that maximizes future rewards. But Instead of maximizing future rewards, future discounted return (<math>R_t = \sum_{t' = t}^T \gamma^{t' - t} r_{t'}</math>) is maximized. <math>\gamma</math> is the discount factor and <math>T</math> is the finishing time step of the game. One of the reasons of using a discount factor is to avoid the sum of becoming infinite so that it can converge. Optimal action-value function <math>Q^*(s, a)</math> is defined as maximum expected return by following any strategy <math>\pi</math>, after seeing sate <math>s</math> and doing action <math>a</math>,
:<math>
Q^*(s, a) = \max_{\pi} \mathbb{E}\left[R_t | s_t = s, a_t = a, \pi\right]. \quad(1)
</math>
This formula obeys [https://en.wikipedia.org/wiki/Bellman_equation Bellman equation]. Meaning that, if the optimal value <math>Q^*(s', a')</math> of state <math>s'</math> is known at the next time step for all possible actions <math>a'</math>, the optimal strategy is choosing action <math>a'</math> that maximizes the expected value of <math>r + \gamma Q^*(s', a') </math>,
:<math>
Q^*(s, a) = \mathbb{E}_{s' \in \varepsilon}\left[r + \gamma \max_{a'} Q^*(s', a') | s, a\right].\quad(2)
</math>
Therefore, the basic idea of value iteration algorithms is to iteratively update the action-value function by using Bellman equation. This converges to the optimal action-value function as the iterations go to infinity. This is impractical because the function is estimated separately for each state, without generalization. In practice, a function approximator is used to estimate it which can be linear or nonlinear. Neural networks are nonlinear function approximators. If the parameters of the network is <math>\theta</math>, the loss function at each iteration <math>i</math> will be as follows.
:<math>
L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.)}\left[(y_i - Q(s, a; \theta_i))^2\right], \quad y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma \max_{a'}Q(s', a'; \theta_{i-1})\right] \quad(3)
</math>
<math>y_i</math> is the target value for iteration <math>i</math>. The loss function simply tries to minimize the squared error between the predicted value of action-value function given current parameters and target value given previous parameters which is easily computed using bellman equation. <math>\rho(s, a)</math> is called the behaviour distribution and is simply the distribution over states and actions. The derivative of the loss function is as follows.
:<math>
\nabla L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(.) | s' \sim \varepsilon}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_i)\right) \nabla_{\theta_i} Q(s, a; \theta_i)\right] \quad(4)
</math>
In order to make gradient updates less computationally expensive, single samples from the behaviour distribution is used instead of using the full expectation. This distribution is often selected by an <math>\epsilon</math>-greedy approach. Moreover, the algorithm is model free and off policy.

==== Deep Reinforcement Learning ====
The goal of the paper is doing reinforcement learning using deep networks on Atari games without any preprocessing on the data. It's worth noting that combining model free reinforcement learning algorithms like Q-learning with non linear approximators or off policy learning can cause the network to diverge. Although this can partially be addressed by gradient temporal difference, the problem of using deep RL still remains a challenging problem.

In order to be able to use machine learning techniques on the problem, an experience replay technique should be used. This is simply storing the previous experiences <math>e_t = (s_t, r_t, s_{t+1})</math> into a replay memory <math>\mathcal{D}</math>. The pseudo code of the algorithm is shown below. In each time step of the game, Q-learning updates are applied to random samples of experiences stored in memory. After that, an action is chosen based on an <math>\epsilon</math>-greedy approach meaning that for probabilities below <math>\epsilon</math> a random action is chosen instead of the best possible action. <math>\phi</math> is a function that is used to produce fixed length representations for histories.

===== Deep Q-learning with experience replay =====
1. Initialize replay memory D to capacity N
2. Initialize action-value function Q with random weights
3. for episode = 1, M do
4. Initialize sequence s1 = {x1} and preprocessed sequenced φ1 = φ(s1)
5. for t = 1, T do
6. With probability ε select a random action at
7. otherwise select at = maxa Q∗(φ(st), a; θ)
8. Execute action at in emulator and observe reward rt and image xt+1 Set st+1 = st, at, xt+1 and preprocess φt+1 = φ(st+1)
9. Store transition (φt, at, rt, φt+1) in D
10. Sample random minibatch of transitions (φj , aj , rj , φj +1 ) from D
11. if φj+1 is terminal
12. Set yj = rj
13. else
14. Set yj = rj + γ max_a′ Q(φj+1, a′; θ)
15. Perform a gradient descent step on (yj − Q(φj , aj ; θ))^2
16. end for
17. end for

This approach has three main advantages compared to approaches such as online Q-learning:
* It is more efficient as each step of experience is used in many weight updates.
* The updates are less variant as samples are chosen randomly instead of consecutively and this breaks the correlation between samples to some extent.
* In on-policy learning, the current parameters of the network determine the next data samples that the parameters should be trained on. As a result, if the maximizing action is to move left then data samples are dominated by the left hand side of the image. This will result in unwanted feedback loops or being stuck in local minima. Experience replay avoids such problems as behaviour distribution is averaged over its previous states, smoothing out learning and avoiding oscillations in parameters.
The proposed algorithm by the paper uses uniform sampling with a memory buffer of size <math>N</math>. However, this approach gives equal importance to all experiences and does not differentiate important transitions. A better sampling technique may be the one that puts more emphasis on transitions from which the model learns the most.

Training on the original pixel images of Atari is computationally expensive. Therefore, a preprocessing stage is used for resizing the images and converting them to grey scale. Besides, there are multiple ways to parametrize Q function using a neural network. This paper uses a convolutional architecture with only the state representation as input and multiple outputs corresponding to each action. Therefore, the network has one forward pass and Q values can be computed for all actions in each state. There are three hidden layers in the network and the final layer is a fully connected layer with a single output for each possible action.

==== Experiments ====
The model is trained with the same parameters for all different games. The only change is the scaling of the reward function: positive rewards are fixed to 1 and negative rewards are fixed to -1 with 0 being the unchanged rewards. Besides, the paper uses a frame-skipping technique that is instead of choosing actions in each frame, the actions are chosen every k frames and the last action is repeated in skipped frames. This will allow the agent to play roughly k times more without significantly increasing the runtime.
[[File:Qlearning eval.png|1200px||thumb|'''Figure 1.''' Two figures on the left show the average reward per episode metric while the two on the right show the estimated Q function.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]

As with any machine learning algorithm, the results should be evaluated. Here, one reasonable choice might be tracking the average total reward metric. But, this tends to be very noisy as the small changes in weights of the network can result in big changes of the distribution. Therefore, a more stable metric can be the estimated value of the action-value function <math>Q</math> which shows how much discounted reward can be obtained by following a policy in a given state. Figure 1 shows the comparison between these two metrics for evaluation.

[[File:Qlearning table.png|700px||thumb|'''Table 1.''' Comparing average total reward for different learning methods. Lower table shows the results obtained by different metrics of the proposed model with last row being the best results.<ref name="paper1">V. Minh, et al., Playing Atari with Deep Reinforcement Learning</ref>]]
Table 1 shows different scores obtained by different methods on all the games. One of the scores is the one obtained by human players. The proposed model was able to achieve better results than humans in three of the games (Breakout, Enduro, Pong). Other than that, all final scores achieved by the model are higher than the state of the art methods on Atari games. One reason of getting lower scores than humans in some of the games may be the challenging nature of the game: finding a strategy that extends over long time scales.

==== Conclusion ====
Although obtaining results with deep reinforcement learning have proven to have low convergence rate, the model proposed in this paper was able to achieve state of the art results on Atari games by using experience replay techniques.

=== Rainbow: Combining Improvements in Deep Reinforcement Learning ===
The main essence of this paper is based on an integrated method for extending the DQN algorithm, proposed in the previous paper. Generally, at each time step <math>t</math> the environment provides agent with an observation <math>S_t</math>. In response, the agent selects an action <math>A_t</math> which provides the next reward <math>R_{t+1}</math>, discount factor <math>\gamma_{t+1}</math> and state <math>S_{t+1}</math>. This can be formalized as a [https://en.wikipedia.org/wiki/Markov_decision_process Markov Decision process] <math><S, A, T, r, \gamma></math>. The members of the tuple correspond to the finite set of states, finite set of actions, transition function, reward function and the discount factor respectively. The action is chosen based on the policy <math>\pi</math> which is the distribution over actions. In DQN, parameters are optimized using the loss function proposed in equation (3). There are several limitations to this algorithm which are addressed by different methods. Some of these extensions are as follows:
* Double Q-learning: Learning in DQN is affected by an overestimation bias in the maximization step performed on loss function in equation (3). This can be addressed by decoupling the selection of the action from its evaluation. Therefore, the target value in the loss function will be changed as follows <ref>Hado van Hasselt, Arthur Guez, David Silver, Deep Reinforcement Learning with Double Q-learning</ref>.
:<math>
y_i = \mathbb{E}_{s' \sim \varepsilon}\left[r + \gamma Q(s', \arg\max_{a'}Q(s', a'; \theta_{i-1}); \theta_{i-1})\right]
</math>
* Prioritized replay: In DQN, the samples are chosen uniformly from the replay memory. However, the samples from which the network learns the most should be chosen more frequently. The idea is using prioritized experience replay<ref>Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver, Prioritized Experience Replay</ref>. Therefore, transitions that are relevant to the last encountered [https://en.wikipedia.org/wiki/Temporal_difference_learning TD] error will have higher probabilities and are chosen most of the times.
* Dueling networks: This is a neural network architecture which is designed for value based reinforcement learning. So, instead of using a convolutional neural network to approximate action-value function in DQN, a shared convolutional encoder along with a special aggregator<ref>Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Marc Lanctot and Nando de Freitas, Dueling Network Architectures for Deep Reinforcement Learning</ref> is used.
* Multi-step Learning
* Distributional RL
* Noisy Nets

== Annotated Bibliography ==
Put your annotated bibliography here. Add links where appropriate.
{{Reflist|group!=note}}

[https://arxiv.org/pdf/1312.5602.pdf V. Minh, et al., Playing Atari with Deep Reinforcement Learning]

[https://arxiv.org/pdf/1710.02298.pdf M. Hessel, et. al., Rainbow: Combining Improvements in Deep Reinforcement Learning]

== To Add ==
Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

{{cc-by-nc-sa-3.0}}

Course:CPSC522/Deep Reinforcement Learning

2018-03-18T06:33:56Z

AINAZHAJIMORADLOU: /* Conclusion */

Course:CPSC522/Deep Reinforcement Learning

2018-03-18T06:23:10Z

AINAZHAJIMORADLOU: /* Experiments */

File:Qlearning table.png

2018-03-18T06:19:47Z

AINAZHAJIMORADLOU: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=evaluation table}}
|date=2018-03-17 23:19:00
|source=Playing Atari with deep reinforcement learning
|author=V. Minh, et. al.
|permission=
|other_versions=
}}

=={{int:license-header}}==
{{subst:uwl}}

[[Category:Uploaded with UploadWizard]]

Course:CPSC522/Deep Reinforcement Learning

2018-03-18T06:10:48Z

AINAZHAJIMORADLOU: /* Experiments */

Course:CPSC522/Deep Reinforcement Learning

2018-03-18T06:10:25Z

AINAZHAJIMORADLOU: /* Experiments */

Course:CPSC522/Deep Reinforcement Learning

2018-03-18T06:09:54Z

AINAZHAJIMORADLOU: /* Experiments */

Course:CPSC522/Deep Reinforcement Learning

2018-03-18T06:09:10Z

AINAZHAJIMORADLOU: /* Content */