UBC Wiki - User contributions [en]

Course:CPSC522

2020-04-25T19:11:21Z

TommasoDAmico: rearranged future combinations 2020 for marking consistency

{{Infobox_New_Course

|title=CPSC 522 Wiki

|picture=Image:wiki.png

|subject code=CPSC

|course number=522

|instructor=David Poole

|email=poole@cs.ubc.ca

|office= 109
|office hours= after class every day
|classroom= DMP 101

}}

[[Category:CPSC522]]
Welcome to [http://www.cs.ubc.ca/~poole/cs522/2019 CPSC 522] Wiki. This is where the participants are writing the textbook. See
http://www.cs.ubc.ca/~poole/cs522/2020/ for the main web page for the course.
==The 2020 Rules==
* These rules are editable, so you can change the rules.
* [[Course:CPSC522/StudentPresentations2020|2020 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 2 students per day.
* [[Course:CPSC522/January2020|January and February Assignment]]<nowiki/>s describes your assignments for January and February.
* [[Course:CPSC522/MarchApril2020|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

==Old (2018, 2019) Rules==
*[[Course:CPSC522/StudentPresentations2018|2018 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 3 students per day.
* [[Course:CPSC522/January2018|January Assignment]] describes your assignment for January.
* [[Course:CPSC522/February2018|February Assignment]] describes your assignment for February.
* [[Course:CPSC522/MarchApril2018|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

== Guidelines ==
* Keep each page as simple as possible (but not simpler); if a page starts to get complicated, consider splitting it.
* Write pages for your peers; they should all be written for incoming graduate students, and only assume background knowledge that is common among such students.
* All pages should obey the [[Course:CPSC522/Conventions|Syntax Conventions]]. If there is a design decision that you need to make that may have non-local implications, add it to the conventions.
* It should use formalism and mathematics when (and only when) the formalism make the description clearer. Use the code tags for math, e.g., <math>P(h\mid e) = \frac{P(h\land e)}{P(e)}.</math> It is worth your while to learn [https://www.latex-project.org/ Latex] if you don't already know it.
* If there is a simple case, and a more general case, give the simple case first. Making things complicated is easy; keeping them simple is difficult and we should strive for simplicity. Any complication needs to be carefully motivated.
* Use the "discussion" tab

Each Page should contain:
* A clear jargon-free description of what is going on. Keep jargon to a minimum.
* Motivating example(s) and, where appropriate, a simple pedagogical example (which may be different from the motivating examples) that is used to explain what is going on
* An argument of plausibility
* Evidence that it works
* Code and pseudo-code, where appropriate. This code should interact with other related code (e.g., [http://aipython.org AIFCA Python Distribution]) if possible. The code should be as simple as possible to implement the techniques. Consider adding exercises as to what can be improved or made more general or bullet-proof. Use a <code>code block</code> for (pseudo-)code (even multi-line code). You can also use the format in http://wiki.ubc.ca/Course:CPSC_320/Midterm_2_Reference_Sheet#Pseudocode (try both and see which better suits your needs).

==Foundations==
Please add your page here and in the [[Course:CPSC522/Index|Index]].

* [[Course:CPSC522/MyTest|My Test]]
===General===
* [[Course:CPSC522/AGI|Artificial General Intelligence]] (2018)
* [[Course:CPSC522/Swarm_Intelligence|Swarm Intelligence]] (2018)

===Control===
* [[Course:CPSC522/Control Theory|Control Theory]] (2016)
* [[Course:CPSC522/Hierarchical Control|Hierarchical Control]] (2016)

===Probability and Graphical Models===
* [[Course:CPSC522/Probability|Probability]] (2016)
* [[Course:CPSC522/Graphical Models|Graphical Models]] (2016)
* [[Course:CPSC522/Bayesian Networks|Bayesian Networks]] (2016)
* [[Course:CPSC522/Markov_Networks|Markov Networks]] (2016)
* [[Course:CPSC522/WeightedModelCounting|Weighted Model Counting]](2019)
====Temporal Models====
* [[Course:CPSC522/Markov Chains|Markov Chains]] (2018)
* [[Course:CPSC522/Hidden_Markov_Models|Hidden Markov Models]] (2016)
* [[Course:CPSC522/Kalman_filter|Kalman filter]] (2018)
* [[Course:CPSC522/Dynamic Bayesian Networks|Dynamic Bayesian Networks]] (2018)
====Inference====
* [[Course:CPSC522/Variable Elimination|Variable Elimination]] (2016)
* [[Course:CPSC522/MCMC|Markov Chain Monte Carlo]] (2016)
* [[Course:CPSC522/Particle Filtering|Particle Filtering]] (2016)
* [[Course:CPSC522/Treatment of Missing Data|Treatment of Missing Data]] (2019)
* [[Course:CPSC522/Bayesian Coresets|Bayesian Coresets]] (2019)
* J0 [[Course:CPSC522/Variational Inference|Variational Inference]] (2020)

====Causality====
* [[Course:CPSC522/Causality|Causality]] (2016)
====Representations of Conditional Probability====
* [[Course:CPSC522/Neural Network|Neural Network]] (2016)
* [[Course:CPSC522/Recurrent Neural Networks|Recurrent Neural Networks]] (2018)
* [[Course:CPSC522/Decision_Trees|Decision Trees]] (2018)
====Learning====
* [[Course:CPSC522/Learning Probabilistic Models with Complete Data|Learning Probabilistic Models with Complete Data]] (2018)
* [[Course:CPSC522/Support_Vector_Machines|Support Vector Machines]] (2018)
* [[Course:CPSC522/Ensemble Learning|Ensemble Learning]] (2018)
* J1 [[Course:CPSC522/Principal_Component_Analysis|Principal Component Analysis (PCA)]] (2020)
* J2 [[Course:CPSC 522/Self-Organizing Maps|Self-Organizing Maps]] (2020)
* F1 [[Course:CPSC 522/Progressive Neural Network|Progressive Neural Network]] (2020)
* F5 [[Course:CPSC522/Conditional GANs for Image to Image Translation|Conditional GANs for Image-To-Image Translation]] (2020)
===NLP===
* [[Course:CPSC522/Natural Language Processing | Natural Language Processing]] (2018)
* [[Course:CPSC522/PCFG|Probabilistic Context Free Grammars]] (2018)
===Utility and Preferences===

* [[Course:CPSC522/Bounded Rationality|Bounded Rationality]] (2018)
* [[Course:CPSC522/Elicitation of Factored Utilities|Elicitation of Factored Utilities]] (2019)

===Acting Under Uncertainty===
* [[Course:CPSC522/Decision Networks|Decision Networks]] (2016)
* [[Course:CPSC522/Markov Decision Process|Markov Decision Process]] (2016)
* F0 [[Course:CPSC522/Partially Observable Markov Decision Processes|Partially Observable Markov Decision Processes]] (2020)
* [[Course:CPSC522/Reinforcement Learning|Reinforcement Learning]] (2016)
* [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning with Function Approximation]] (2016)
* [[Course:CPSC522/Game Theory|Game Theory]] (2016)
* [[Course:CPSC522/Multi-Agent Systems|Multi-Agent Systems]] (2018)
* [[Course:CPSC522/Stochastic Optimization|Stochastic Optimization]] (2018)
* [[Course:CPSC522/Value of Information and Control|Value of Information]] (2019)

===Logic===
* [[Course:CPSC522/Abduction|Abduction]] (2018)
* [[Course:CPSC522/Knowledge Compilation|Knowledge Compilation]] (2016)
* [[Course:CPSC522/Predicate Calculus|Predicate Calculus]] (2016)
* [[Course:CPSC522/Markov Logic|Markov Logic]] (2018)
* [[Course:CPSC522/Higher Order Logic|Higher Order Logic]] (2018)
* [[Course:CPSC522/Ontology|Ontology]] (2019)

==Existing Combinations (2016)==
* [[Course:CPSC522/Recommendation System using Matrix Factorization|Recommendation System using Matrix Factorization]]
* [[Course:CPSC522/Latent Dirichlet Allocation|Latent Dirichlet Allocation]]
* [[Course:CPSC522/Deep Neural Network|Deep Neural Network and Game of Go]]
* [[Course:CPSC522/Problog|Problog]]
* [[Course:CPSC522/Maximum Entropy Markov Models|Maximum Entropy Markov Models]]
* [[Course:CPSC522/Future Directions for Semantic Systems|Ontology Search Engine]]
* [[Course:CPSC522/Convolutional Neural Networks|Convolutional Neural Networks]]
* [[Course:CPSC522/Learning Markov Logic Network Structure|Learning Markov Logic Network Structure]]
* [[Course:CPSC522/Decision Support System using Interactive Preference Elicitation|Decision Support System using Interactive Preference Elicitation]]
* [[Course:CPSC522/Predicting Affect of User's Interaction with an Intelligent Tutoring System|Predicting Affect of User's Interaction with an Intelligent Tutoring System]]
* [[Course:CPSC522/Record Linkage and identity uncertainty|Record Linkage and identity uncertainty]]
* [[Course:CPSC522/Robot Scientist|Robot Scientist]]
* [[Course:CPSC522/Density-Based Unsupervised Learning|Density-Based Unsupervised Learning]]
* [[Course:CPSC522/Predicting Human Behavior in Normal-Form Games|Predicting Human Behavior in Normal-Form Games]]
* [[Course:CPSC522/Identity Uncertainty|Identity Uncertainty]]
* [[Course:CPSC522/Generative Adversarial Networks|Generative Adversarial Networks]]

* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
*[[Course:CPSC522/User-Adaptive Information Visualization|User-Adaptive Information Visualization]]

==Existing Combinations (2020)==
* J3 [[Course:CPSC522/Monte Carlo Localization |Pedestrian localization for Indoor Environments]] (2020)
* J4 [[Course:CPSC522/Automation of hypothesis generation and testing in science|Automation of hypothesis generation and testing in science]] (2020)
* J5 [[Course:CPSC522/Deep Q Network |Prioritized Experience Replay]] (2020)
* F2 [[Course:CPSC522/Variation Auto-Encoders |Variational Auto-Encoders]] (2020)
* F3[[Course:CPSC522/Combining_Collaborative_Filtering_with_Personal_Agents_for_Better_Recommendations | Hybrid Recommendation Systems]] (2020)
* F4 [[Course:CPSC522/Online Pattern Analysis by Evolving Self-Organizing Maps|Online Pattern Analysis by Evolving Self-organizing Maps]] (2020)

==Existing Combinations (2018)==
===Neural Networks===
* [[Course:CPSC522/Financial Forecasting using LSTM Networks |Financial Forecasting using LSTM Networks]] (2018)
* [[Course:CPSC522/Character Level Language Models using LSTM|Character Level Language Models using LSTM]] (2018)
* [[Course:CPSC522/TextSummarizationUsingMachineLearning |Text Summarization using Machine Learning]] (2018)
* [[Course:CPSC522/Password_cracking_using_PCFGs_and_Neural_Networks|Password Cracking using Probabilistic Context Free Grammars and Neural Networks]] (2018)
* [[CNNs in Image Segmentation]](2018)
* [[Course:CPSC522/Image_Classification_With_Convolutional_Neural_Networks|Image Classification With Convolutional Neural Networks]] (2018)
* [[Image Colourization using Deep Learning]](2018)
* [[Course:CPSC522/StackedGAN|Stacked Generative Adversarial Networks]] (2018)

===Reinforcement Learning===
* [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] (2018)
* [[Course:CPSC522/Deep_Reinforcement_Learning|Deep Reinforcement Learning]] (2018)
* [[Course:CPSC522/Self_Improving_Machines|Self-Improving Machines]] (2018)
* [[Course:CPSC522/Adaptive_Network_Routing_using_ACO|Adaptive Network Routing using Ant Colony Optimization]] (2018)

===Decision-theoretic Planning===
* [[Course:CPSC522/Action_Selection_for_MDPs|Action Selection for MDPs]] (2018)
* [[Course:CPSC522/Rao_Blackwellized_Particle_Filtering|Rao-Blackwellized Particle Filtering]](2018)
===Relational Reasoning===
* [[Course:CPSC522/Transfer_Learning_with_Markov_Logic|Transfer Learning with Markov Logic]] (2018)
* [[Course:CPSC522/Cognitive_Robotics|Cognitive Robotics]] (2018)
===Applications===
* [[Course:CPSC522/Affect Prediction using Eye Gaze|Affect Prediction using Eye Gaze]] (2018)
* [[Course:CPSC522/Conflict-Driven Clause Learning for the Boolean Satisfiability Problem|Conflict-Driven Clause Learning for the Boolean Satisfiability Problem]] (2018)

==Existing Combinations (2019)==
* [[Course:CPSC522/Ontology Extraction|Ontology Extraction]]
* [[Course:CPSC522/Restricted Boltzmann Machines for Collaborative Filtering|Restricted Boltzmann Machines for Collaborative Filtering]]
* [[Course:CPSC522/Minimax Regret Preference Elicitation for Risky Prospects|Minimax Regret Preference Elicitation for Risky Prospects]]
* [[Course:CPSC522/Sequential Monte Carlo samplers|Sequential Monte Carlo samplers]]
* [[Course:CPSC522/FastSLAM|FastSLAM]]
* [[Course:CPSC522/SMC for PGMs|Sequential Monte Carlo for Probabilistic Graphical Models]]

==Future combinations (2016)==
* [[Course:CPSC522/Sentiment Analysis|Sentiment Analysis: Movie Reviews]]
* [[Course:CPSC522/Collaborative Filtering|Collaborative Filtering]]
* [[Course:CPSC522/List Recommendation|List Recommendation]]
* [[Course:CPSC522/Inactive Cookie Mapping via Trail Matching|Inactive Cookie Mapping via Trail Matching]]
* [[Course:CPSC522/Improve recommendation system by integration|Improve Recommendation System by Integration]]
* [[Course:CPSC522/Identity Uncertainty in a restaurant data-set|Identity Uncertainty in a restaurant data-set]]
* [[Course:CPSC522/Regularization_for_Neural_Networks|Regularization for Neural Networks]]
* [[Course:CPSC522/Spam Detection|Spam Detection]]
* [[Course:CPSC522/Titanic: Machine Learning from Disaster|Titanic: Machine Learning from Disaster]]
* [[Course:CPSC522/Automatic Classification of Morphological Heart Arrhythmia | Automatic Classification of Morphological Heart Arrhythmia]]
* [[Course:CPSC522/Linking Sentences in Asynchronous Conversations|Linking Sentences in Asynchronous Conversations]]
* [[Course:CPSC522/Generic Aspect-based Aggregation of Sentiments|Generic Aspect-based Aggregation of Sentiments]]
* [[Course:CPSC522/Graph Based keyword extraction|Graph Based Key-corporation Extraction]]
* [[Course:CPSC522/Improving the accuracy of Affect Prediction in an Intelligent Tutoring System|Improving the accuracy of Affect Prediction in an Intelligent Tutoring System]]
* [[Course:CPSC522/Improving Human Behavior Prediction in Simultaneous-Move Games|Improving Human Behavior Prediction in Simultaneous-Move Games]]
* [[Course:CPSC522/The Automation of Disease Diagnosis|The Automation of Disease Diagnosis]]
* [[Course:CPSC522/Analyzing online dating trends with Weka|Analyzing online dating trends with Weka]]

==Future combinations (2018)==
* [[Course:CPSC522/Artificial Intelligence and Economic Theory|Artificial Intelligence and Economic Theory]]
* [[Course:CPSC522/Weak Semantic Map|Weak Semantic Map: Simplified Chinese]]
* [[Course:CPSC522/Network Agent|Datacenter Traffic as Reinforcement Learning Problem]]
* [[Course:CPSC522/Baseilne_of_RSI|A Theoretical Baseline of Recursive Self-improvement]]
* [[Course:CPSC522/Text_Summarization_for_busy_people!| Text summarization for busy people!!]]
* [[Course:CPSC522/An_evaluation_on_selecting_and_applying_Recommendation_Methods | An evaluation on selecting and applying Recommendation Methods]]
* [[Course:CPSC522/Learning User Preferences of Motion Control | Learning User Preferences of Motion Control]]
* [[Course:CPSC522/Experiments_with_Reinforcement_Learning| Experiments with Reinforcement Learning]]
* [[Course:CPSC522/A_Comparison_of_LDA_and_NMF_for_Topic_Modeling_on_Literary_Themes| A Comparison of LDA and NMF for Topic Modeling on Literary Themes]]
* [[Course:CPSC522/Analysis of hierarchical prior for Language modeling | Analysis of hierarchical prior for Language modeling]]
* [[Better_caching_using_reinforcement_learning|Better Caching using reinforcement learning]]
* [[Course:CPSC522/Evaluation_of_ACO|Evaluating Ant Colony Optimization in a simulation]]
* [[Course:CPSC522/SLAM_And_Sensor_Quality|SLAM and Sensor Quality]]
* [[Text generation with LSTM and Markov Chain]]
* [[Course:CPSC522/Topology_and_Embedding_Multi-relational_Data|Topology and Embedding Multi-relational Data]]

== Future combinations (2019) ==
* [[Course:CPSC522/Reinforcement Learning with Linear Model of Reward Corruption|Reinforcement Learning with Linear Model of Reward Corruption]]
*
* [[Course:CPSC522/Adverserial Belief Propagation|Adversarial Belief Propagation]]
*
* [[Course:CPSC522/Using Subset Information with Matrix Factorization|Using Subset Information with Matrix Factorization]]
*
* [[Course:CPSC522/Learning Attention via Active Inference|Learning Attention via Active Inference]]
* [[Course:CPSC522/Regularization as an Alternative to Negative Sampling in KGs|Regularization as an Alternative to Negative Sampling in KGs]]
== Future combinations (2020) ==
* M0 [[Course:CPSC522/Grouped Prioritized Experience Replay (GPER)|Grouped Prioritized Experience Replay (GPER)]]
* M1 [[Course:CPSC522/Alternative_Classifiers|Alternative Classifiers]]
* [[Course:CPSC522/Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations|M2 Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations]]
* M3 [[Course:CPSC522/Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps|Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps]]
==Suggested Unclaimed Pages==
Here are some possible topics for pages. This list is not meant to limit your imagination. Some of them might be better split into multiple pages. There are many other possible topics.

When claimed, these pages should be moved from this section to the table of contents above and to the [[Course:CPSC522/Index|Index]] of existing pages. To claim a page you have to actually create it and edit it (and have your name on the page, so everyone can see who has claimed it).

* [[Course:CPSC522/Probability general semantics|Probability - general semantics]] with infinitely many variables and/or variables with infinite domains
* [[Course:CPSC522/Representations of Conditional Distributions|Representations of Conditional Distributions]]
* [[Course:CPSC522/Recursive Conditioning|Recursive Conditioning]]
* [[Course:CPSC522/Parity Methods|Parity Methods for Probabilistic Inference]]
* [[Course:CPSC522/Matrix Factorization|Matrix Factorization]]
* [[Course:CPSC522/Utility|Utility]]
* [[Course:CPSC522/Multi-Attribute Utility|Multi-Attribute Utility]]
* [[Course:CPSC522/Preference Elicitation|Preference Elicitation]]
* [[Course:CPSC522/Mechanism Design|Mechanism Design]]
* [[Course:CPSC522/Logic Programming|Logic Programming]]
* [[Course:CPSC522/Negation as Failure|Negation as Failure]]
* [[Course:CPSC522/Equality-Identity|Equality/Identity]]
* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
* [[Course:CPSC522/Ontologies|Ontologies]]
* [[Course:CPSC522/Continual Learning|Continual Learning]]

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-24T19:52:57Z

TommasoDAmico:

== Grouped Prioritized Experience Replay (GPER) ==
This page explores the concept of grouping prioritized experience replay memories to improve learning efficiency in temporal difference reinforcement learning environments.

Principal Author: Obada Alhumsi, Tommaso D’Amico

Collaborators:

== Abstract ==
Grouped Prioritized Experience Replay is a hypothetical extension of Prioritized Experience Replay where prioritization is done by grouped experiences rather than individual state action pairs. The page below explores the effectiveness of this method with respect to Q-Learning, Q-Learning with experience replay and Q-Learning with prioritized experience replay.

=== Builds on ===
Grouped Prioritized Experience Replay builds upon [https://wiki.ubc.ca/Course:CPSC522/Deep_Q_Network Prioritized Experience Replay] which in turn builds upon the concept of Experience Replay in [https://wiki.ubc.ca/Course:CPSC522/Deep_Q-Learning Temporal Difference Learning]. The algorithms will use [[Course:CPSC522/Reinforcement Learning with Function approximation|Q-Learning]] as a fundamental building block.

=== Related Pages ===
[https://wiki.ubc.ca/Course:CPSC522/Deep_Q_Network Deep-Q Networks] are used instead of Q-Learning to apply these algorithms in continuos learning environments.

Experience Replay is also tightly related to [https://en.wikipedia.org/wiki/Hippocampal_replay Hippocampal Replay] in the literature.

== Content ==

=== Introduction ===
Grouped Prioritized Experience Replay is a hypothetical extension of Prioritized Experience Replay where prioritization is done by grouped experiences rather than individual state-action pairs. The intention is to render learning more efficient by prioritizing experience replay to specific action or state groups with which the agent is most uncertain about. This extension is motivated by training excersices seen in a variety of sports, where an athlete repeatedly preforms actions in a set of similar envrionment states or performs similar actions in a set of random environment states. The former can be seen in soccer, where the grouped training excersices include training freekicks, cornerballs, counterattacks and other more complicated states that the game presents. The latter can be seen in table tennis, where the grouped training excersices include training a players forehand return( hitting the ball with the red side of the paddle) and backhand return(hitting the ball with the black side of the paddle). This project explores the effectiveness of this method with respect to Q-Learning, Q-Learning with experience replay and Q-Learning with prioritized experience replay.

=== Background ===

==== Temporal Difference Learning & TD Error ====
Temporal Difference Learning can be more easily understood in comparison to its conterparts methods such as monte carlo methods. In Temporal Difference Learning, the predictions of current states based on the environment are updated with each new time step, unlike Monte Carlo Methods where these are only updated at the end of an episode. This means that while an agent is actively exploring its environment, the feedback it receives influences its predictions of the current state at each time step. The TD error function reports back the difference between the estimated reward at any given state or time step and the actual reward received. Temporal difference is the basis of algorithms such as Q-learning, TD(0) and SARSA.

==== Experience Replay ====
Experience Replay is an extension of Q-learning where instead of just running Q-learning on state-action pairs as they occur, the agent stores these state-actions pair experiences and updates them based on future experiences that occur, essentially introducing the concept of memory to the algorithm. This way the algorithm has more efficient use of its experiences and is able to learn faster than standard Q-learning.

==== Prioritized Experience Replay ====
Prioritized Experience Replay attempts to optimize Experience Replay to areas where the agent is more uncertain of its actions by prioritizing experiences with a high temporal-difference error (with some stochastic elements). This allows the agent to learn more quickly by avoiding going over experiences it has mastered and focusing on the ones where it seems to be making more mistakes. By doing so Prioritized experience replay allows for more valuable memory storage as only relevant experiences remain stored and are replayed. For more detailed information on this topic visit the page on Deep-Q Networks.

=== Hypothesis ===
The hypothesis to be tested is that the concept of grouping priorities in experience replay by state or action can improve training efficiency and minimize error for temporal difference learning algorithms in comparison to plain Q-Learning, Q-Learning with Experience Replay and Q-Learning with Prioritized Experience Replay.

=== Algorithm ===
Grouped Prioritized Experience Replay is a type of prioritization focused on groups rather than individual experiences. In order to acomplish group prioritization, after each time step, the memory of the last experience is stored according to its groupping. The TD Error of all stored experiences are then calculated and each group average TD error is obtained. The group with the highest average TD error is then sampled from at uniform.

For example, if grouping is done by action, after a certain time step, if the agent moved up, the resulting experience will be placed under the action group "move up". The error of each experience is then calculated and averaged for each group. It may be that the agent is most uncertain of movements to the left, therefore those experiences will be replayed, ideally improving its performance "going left" more quickly.
[[File:GPER_Pseudo-code.png|center|thumb|463x463px|Simple implementation of the GPER sampling algorithm]]

=== Testing ===
[[File:Taxi-v3.png|thumb|Taxi-v3 Game Environment Render]]

==== Test Environment ====
The testing for this algorithm was done using a modified version of the [https://gym.openai.com/envs/Taxi-v3/ Taxi-v3 game] environment present in the [https://gym.openai.com/envs/#toy_text OpenAi Gym Library].
[[File:Taxi-v3 full.png|thumb|Taxi-v3 Game with Passenger inside Taxi]]
In the original Taxi-v3 game and in the modified version the taxi starts off at a random square and the passenger is at a random location. The taxi drives to the passenger's location, picks up the passenger, drives to the passenger's destination and then drops off the passenger. Once the passenger is dropped off, the episode ends.

The following are the labels demonstrated in the render of the game:
* letters and numbers (R, G, B, Y, 0-7): locations for passenger and destinations
* blue: passenger
* magenta: destination
* yellow: empty taxi
* green: full taxi
[[File:Taxi mod big.png|thumb|Modified Taxi-v3 game environment]]
The modified version of the game is an extention of the map and an increase in locations and destinations for the passanger. This was done in an effort to obtain a larger discrete environment to train the algorithms on to more suitably display the differences in training efficiency.

The original Taxi-v3 game has 500 states (5 x-axis positions, 5 y-axis positions, 4 destination locations and 5 passanger locations) and 6 actions (move up, move down, move left, move right, pickup passenger and dropoff passenger).

The Modified Taxi game has 28800 states (20 x-axis positions, 20 y-axis positions, 8 destination locations and 9 passanger locations) and the same 6 actions as the original.

Rewards in the modified Taxi game were given as follows:
* -1 for movement
* -1 for wrong dropoff or pickup
* +100 for successful dropoff
Wrongful dropoff and pickup have been ket at a low penalty to avoid the agent from learning to avoid the action faster than it would find the reward. This was done as during fine tuning it was found that the agents would often be stuck in local minima where they would just move back around until the end of the episode.

==== Methodology ====
In order to test the performance of Grouped Prioritized Experience Replay a set of algorithms was used as baseline for performance. Since GPER builds upon other concepts the following algorithms were used in comparison:
* Q-Learning
* Q-Learning with Experience Replay
* Q-Learning with Proportional Prioritized Experience Replay
* Q-Learning with Rank-Based Prioritized Experience Replay
* Q-Learning with GPER action grouping (6 groups)
* Q-Learning with GPER x-y position state grouping (4 groups, each group makes a quadrant of the grid)
* Q-Learning with GPER destination location grouping (8 groups)
* Q-Learning with GPER passenger location grouping (9 groups)
All algorithms were trained with the same parameters and environment to avoid biases.

==== Results ====
For the results below the algorithms have played through 40000 games of Modified Taxi-v3 with a limit of 900 turns per game.

The table below summarizes some values from the results:
{| class="wikitable"
|+Scores of each algorithm over 40000 episodes of Modified Taxi-v3
!
!Q-Learning
!Experience Replay
!Proportional PER
!Rank-Based PER
!Action GPER
!Passenger Location GPER
!Destination Location GPER
!XY Taxi Location GPER
|-
|Average Reward
|475.49
|499.17
|480.06
|483.38
| -578.94
| -539.39
|183.27
|355.46
|-
|Highest Reward
|991
|991
|990
|990
|991
|991
|991
|991
|-
|Average Episode Length
|318.6
|302.96
|316.74
|313.89
|755.99
|741.19
|435.05
|364.41
|-
|Lowest Episode Length
|9
|9
|10
|10
|9
|9
|9
|9
|}

The following plot represent the reward obtained by the agent at each episode averaged every 100 episodes for each algorithm tested.

Given the rewards of -1 for movement and wrongful actions and +1000 for completing the task the minimum score is of -900 and the maximum will approach +1000.
[[File:Grouped Prioritized Experience Replay Testing Results for Rewards over time.png|center|thumb|1197x1197px|Average rewards over 40000 episodes for each tested algorithm]]

The following plot demonstrates the average episode length for each algorithm over time. In the plot below lower scores are better as it represents the average number of movements it takes for an agent to complete the game over the learning process.
[[File:Grouped Prioritized Experience Replay Testing Results for Episode Length over time.png|center|thumb|1189x1189px|Average Epsiode Length over 40000 episodes for each tested algorithm]]
After plotting these, there seemed to be some ambiguity on the variance of these averages, do curves such as Action GPER actually understand the game but only complete it 1/4 of the time or are they taking 750 steps every episode to complete the tasks? Below is a curve looking at the change in episode lenght over time. This has been further smoothed out to facilitate visualization of the trends.
[[File:Grouped Prioritized Experience Replay Testing Results for change in rewards over time.png|center|thumb|1188x1188px|Average Change in Rewards over 40000 episodes for each algorithm tested]]

=== Discussion ===
From the first plot shown it can be seen that although all algorithms seem to converge, some converge at lower scores than others. As emphasized in the thrid plot this is mainly due to the averaging effect used to clean up the data for visualization. Meaning that most algorithms seem to have reached the maximum highscores although those illustrated with lower averages tended to be more erratic in behaviour, meaning that most episodes they will not successfully terminate the game and are more likely to exert erratic behaviours.

It is possible that with further training these would eventually converge to the global maximum although it appears that they have settled in local maxima. Tuning of the epsylon greedy parameter may help in this case as it would allow these algorithms to explore further scenarious that they seem to not have been exposed to prior.

It can be seen that of the GPER methods tested achieved lower performance compared to prior established algorithms. Provided that the same parameters were used for all trainings and there are no extra parameters introduced in the proposed adaptation, the conclusion may be that the technique does not compare in performance to prior established algorithms.

From the second plot illustrating episode length over time, the tested GPER algorithms never quite learned the game, appearing to not complete most times. For example in Passenger Location GPER the agent seems to run out of steps about 3 out of 4 times it attempts the game. This may be as the passenger location grouping is only relevant to the game for the first component where the agent needs to find the passenger.

The best performing GPER grouping tested seemed to be grouping by XY Taxi coordinates, where the grid is divided into 4 quadrants/groups. Unlike passenger location and destination location grouping, XY grouping is useful throughout the entire game, which could have lead to its increased performance.However, action groupings, which are useful throughout the game as well, did not perform as well. This leads to the idea that state grouping could generally be better than action grouping, nonetheless, further testing on different environment and parameter fine tuning should be performed before coming to such a conclusion.

It is interesting to notice that initially XY Taxi Location GPER also seems to perform on par with the established algorithms. This may be because of the desired effect of grouping seeked by this experiment, where by grouping experiences by relevant states, the algorithm restricts prioritization only to groups considered relevant by the designer, reducing the need for the algorithm to train against redundant behaviours.

In the third plot we see the change in rewards of each algorithm over their learning process. IT can be seen that established algoriths initially have a high variance in their rewards, but converge to have small differences, indicating they have perfected their strategy. The same cannot be said about the GPER algorithms where large differences in score remain constant until the end of the learning process. This indicates that these did not converge to the solution and still only manage to complete the task occasionally.

=== Conclusion and Further Work ===
Overall GPER does not seem to be a better algorithm than currently used algorithms for experience replay in Q-Learning. It does although seems to provide valuable insights to which state types may be relevant for the learning task. From the graphs above there is a clear difference in performance for each grouping which suggests a difference in relevance of each state type to the learning process. This may be relevant to understanding what influences the learning process of an agent over time.

Further testing of these algorithms is required with different environments and paramenters to determine their functionality and usefulness. As shown in the results above, little difference among pre established algorithms can be seen in this particular example, demonstrating that perhaps more eleborate environments are required to highlight their differences.

An aspect that can be further looked at is that of utilizing probability among groups when sampling instead of sampling from the grouping with the worst error every time, this may avoid algorithms getting stuck on a specific issue that may be learned by learning other aspects of the overall task.

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-24T19:06:33Z

TommasoDAmico:

== Grouped Prioritized Experience Replay (GPER) ==
This page explores the concept of grouping prioritized experience replay memories to improve learning efficiency in temporal difference reinforcement learning environments.

Principal Author: Obada Alhumsi, Tommaso D’Amico

Collaborators:

== Abstract ==
Grouped Prioritized Experience Replay is a hypothetical extension of Prioritized Experience Replay where prioritization is done by grouped experiences rather than individual state action pairs. The page below explores the effectiveness of this method with respect to Q-Learning, Q-Learning with experience replay and Q-Learning with prioritized experience replay.

=== Builds on ===
Grouped Prioritized Experience Replay builds upon [https://wiki.ubc.ca/Course:CPSC522/Deep_Q_Network Prioritized Experience Replay] which in turn builds upon the concept of Experience Replay in [https://wiki.ubc.ca/Course:CPSC522/Deep_Q-Learning Temporal Difference Learning]. The algorithms will use [[Course:CPSC522/Reinforcement Learning with Function approximation|Q-Learning]] as a fundamental building block.

=== Related Pages ===
[https://wiki.ubc.ca/Course:CPSC522/Deep_Q_Network Deep-Q Networks] are used instead of Q-Learning to apply these algorithms in continuos learning environments.

Experience Replay is also tightly related to [https://en.wikipedia.org/wiki/Hippocampal_replay Hippocampal Replay] in the literature.

== Content ==

=== Introduction ===
Grouped Prioritized Experience Replay is a hypothetical extension of Prioritized Experience Replay where prioritization is done by grouped experiences rather than individual state-action pairs. The intention is to render learning more efficient by prioritizing experience replay to specific action or state groups with which the agent is most uncertain about. This extension is motivated by training excersices seen in a variety of sports, where an athlete repeatedly preforms actions in a set of similar envrionment states or performs similar actions in a set of random environment states.The former can be seen in soccer, where the grouped training excersices include training freekicks, cornerballs, counterattacks and other more complicated states that the game presents. The latter can be seen in table tennis, where the grouped training excersices include training a players forehand return( hitting the ball with the red side of the paddle) and backhand return(hitting the ball with the black side of the paddle). This project explores the effectiveness of this method with respect to Q-Learning, Q-Learning with experience replay and Q-Learning with prioritized experience replay.

=== Background ===

==== Experience Replay ====
Experience Replay is an extension of Q-learning where instead of just running Q-learning on state-action pairs as they occur, the agent stores these state-actions pair experiences and updates them based on future experiences that occur, essentially introducing the concept of memory to the algorithm. This way the algorithm has more efficient use of its experiences and is able to learn faster than standard Q-learning.

==== Prioritized Experience Replay ====
Prioritized Experience Replay attempts to optimize Experience Replay to areas where the agent is more uncertain of its actions by prioritizing experiences with a high temporal-difference error (with some stochastic elements). This allows the agent to learn more quickly by avoiding going over experiences it has mastered and focusing on the ones where it seems to be making more mistakes. By doing so Prioritized experience replay allows for more valuable memory storage as only relevant experiences remain stored and are replayed. For more detailed information on this topic visit the page on Deep-Q Networks.

=== Hypothesis ===
The hypothesis to be tested is that the concept of grouping priorities in experience replay by state or action can improve training efficiency and minimize error for temporal difference learning algorithms in comparison to plain Q-Learning, Q-Learning with Experience Replay and Q-Learning with Prioritized Experience Replay.

=== Algorithm ===
Grouped Prioritized Experience Replay is a type of prioritization focused on groups rather than individual experiences. In order to acomplish group prioritization, after each time step, the memory of the last experience is stored according to its groupping. The TD Error of all stored experiences are then calculated and each group average TD error is obtained. The group with the highest average TD error is then sampled from at uniform.

For example, if grouping is done by action, after a certain time step, if the agent moved up, the resulting experience will be placed under the action group "move up". The error of each experience is then calculated and averaged for each group. It may be that the agent is most uncertain of movements to the left, therefore those experiences will be replayed, ideally improving its performance "going left" more quickly.
[[File:GPER_Pseudo-code.png|center|thumb|463x463px|Simple implementation of the GPER sampling algorithm]]

=== Testing ===
[[File:Taxi-v3.png|thumb|Taxi-v3 Game Environment Render]]

==== Test Environment ====
The testing for this algorithm was done using a modified version of the [https://gym.openai.com/envs/Taxi-v3/ Taxi-v3 game] environment present in the [https://gym.openai.com/envs/#toy_text OpenAi Gym Library].
[[File:Taxi-v3 full.png|thumb|Taxi-v3 Game with Passenger inside Taxi]]
In the original Taxi-v3 game and in the modified version the taxi starts off at a random square and the passenger is at a random location. The taxi drives to the passenger's location, picks up the passenger, drives to the passenger's destination and then drops off the passenger. Once the passenger is dropped off, the episode ends.

The following are the labels demonstrated in the render of the game:
* letters and numbers (R, G, B, Y, 0-7): locations for passenger and destinations
* blue: passenger
* magenta: destination
* yellow: empty taxi
* green: full taxi
[[File:Taxi mod big.png|thumb|Modified Taxi-v3 game environment]]
The modified version of the game is an extention of the map and an increase in locations and destinations for the passanger. This was done in an effort to obtain a larger discrete environment to train the algorithms on to more suitably display the differences in training efficiency.

The original Taxi-v3 game has 500 states (5 x-axis positions, 5 y-axis positions, 4 destination locations and 5 passanger locations) and 6 actions (move up, move down, move left, move right, pickup passenger and dropoff passenger).

The Modified Taxi game has 28800 states (20 x-axis positions, 20 y-axis positions, 8 destination locations and 9 passanger locations) and the same 6 actions as the original.

Rewards in the modified Taxi game were given as follows:
* -1 for movement
* -1 for wrong dropoff or pickup
* +100 for successful dropoff
Wrongful dropoff and pickup have been ket at a low penalty to avoid the agent from learning to avoid the action faster than it would find the reward. This was done as during fine tuning it was found that the agents would often be stuck in local minima where they would just move back around until the end of the episode.

==== Methodology ====
In order to test the performance of Grouped Prioritized Experience Replay a set of algorithms was used as baseline for performance. Since GPER builds upon other concepts the following algorithms were used in comparison:
* Q-Learning
* Q-Learning with Experience Replay
* Q-Learning with Proportional Prioritized Experience Replay
* Q-Learning with Rank-Based Prioritized Experience Replay
* Q-Learning with GPER action grouping (6 groups)
* Q-Learning with GPER x-y position state grouping (4 groups, each group makes a quadrant of the grid)
* Q-Learning with GPER destination location grouping (8 groups)
* Q-Learning with GPER passenger location grouping (9 groups)
All algorithms were trained with the same parameters and environment to avoid biases.

==== Results ====
For the results below the algorithms have played through 40000 games of Modified Taxi-v3 with a limit of 900 turns per game.

The following plot represent the reward obtained by the agent at each episode averaged every 100 episodes for each algorithm tested.

Given the rewards of -1 for movement and wrongful actions and +1000 for completing the task the minimum score is of -900 and the maximum will approach +1000.
[[File:Grouped Prioritized Experience Replay Testing Results for Rewards over time.png|center|thumb|1180.99x1180.99px|Average rewards over 40000 episodes for each tested algorithm]]

The following plot demonstrates the average episode length for each algorithm over time. In the plot below lower scores are better as it represents the average number of movements it takes for an agent to complete the game over the learning process.
[[File:Grouped Prioritized Experience Replay Testing Results for Episode Length over time.png|center|thumb|1188.99x1188.99px|Average Epsiode Length over 40000 episodes for each tested algorithm]]
After plotting these, there seemed to be some ambiguity on the variance of these averages, do curves such as Action GPER actually understand the game but only complete it 1/4 of the time or are they taking 750 steps every episode to complete the tasks? Below is a curve looking at the change in episode lenght over time. This has been further smoothed out to facilitate visualization of the trends.
[[File:Grouped Prioritized Experience Replay Testing Results for change in rewards over time.png|center|thumb|1188x1188px|Average Change in Rewards over 40000 episodes for each algorithm tested]]

=== Discussion ===
From the first plot shown it can be seen that although all algorithms seem to converge, some converge at lower scores than others. As emphasized in the thrid plot this is mainly due to the averaging effect used to clean up the data for visualization. Meaning that most algorithms seem to have reached the maximum highscores although those illustrated with lower averages tended to be more erratic in behaviour, meaning that most episodes they will not successfully terminate the game and are more likely to exert erratic behaviours.

It is possible that with further training these would eventually converge to the global maximum although it appears that they have settled in local maxima. Tuning of the epsylon greedy parameter may help in this case as it would allow these algorithms to explore further scenarious that they seem to not have been exposed to prior.

It can be seen that of the GPER methods tested achieved lower performance compared to prior established algorithms. Provided that the same parameters were used for all trainings and there are no extra parameters introduced in the proposed adaptation, the conclusion may be that the technique does not compare in performance to prior established algorithms.

From the second plot illustrating episode length over time, the tested GPER algorithms never quite learned the game, appearing to not complete most times. For example in Passenger Location GPER the agent seems to run out of steps about 3 out of 4 times it attempts the game. This may be as the passenger location grouping is only relevant to the game for the first component where the agent needs to find the passenger.

The best performing GPER grouping tested seemed to be grouping by XY Taxi coordinates, where the grid is divided into 4 quadrants/groups. Unlike passenger location and destination location grouping, XY grouping is useful throughout the entire game, which could have lead to its increased performance.However, action groupings, which are useful throughout the game as well, did not perform as well. This leads to the idea that state grouping could generally be better than action grouping, nonetheless, further testing on different environment and parameter fine tuning should be performed before coming to such a conclusion.

It is interesting to notice that initially XY Taxi Location GPER also seems to perform on par with the established algorithms. This may be because of the desired effect of grouping seeked by this experiment, where by grouping experiences by relevant states, the algorithm restricts prioritization only to groups considered relevant by the designer, reducing the need for the algorithm to train against redundant behaviours.

In the third plot we see the change in rewards of each algorithm over their learning process. IT can be seen that established algoriths initially have a high variance in their rewards, but converge to have small differences, indicating they have perfected their strategy. The same cannot be said about the GPER algorithms where large differences in score remain constant until the end of the learning process. This indicates that these did not converge to the solution and still only manage to complete the task occasionally.

=== Conclusion and Further Work ===
Overall GPER does not seem to be a better algorithm than currently used algorithms for experience replay in Q-Learning. It does although seems to provide valuable insights to which state types may be relevant for the learning task. From the graphs above there is a clear difference in performance for each grouping which suggests a difference in relevance of each state type to the learning process. This may be relevant to understanding what influences the learning process of an agent over time.

Further testing of these algorithms is required with different environments and paramenters to determine their functionality and usefulness. As shown in the results above, little difference among pre established algorithms can be seen in this particular example, demonstrating that perhaps more eleborate environments are required to highlight their differences.

An aspect that can be further looked at is that of utilizing probability among groups when sampling instead of sampling from the grouping with the worst error every time, this may avoid algorithms getting stuck on a specific issue that may be learned by learning other aspects of the overall task.

File:Grouped Prioritized Experience Replay Testing Results for change in rewards over time.png

2020-04-24T18:12:28Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Grouped Prioritized Experience Replay Testing Results for change in rewards over time}}
|date=2020-04-24
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

File:Grouped Prioritized Experience Replay Testing Results for Episode Length over time.png

2020-04-24T18:12:28Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Grouped Prioritized Experience Replay Testing Results for Episode Length over time}}
|date=2020-04-24
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

File:Grouped Prioritized Experience Replay Testing Results for Rewards over time.png

2020-04-24T18:12:28Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Grouped Prioritized Experience Replay Testing Results for Rewards over time}}
|date=2020-04-24
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

Thread:Course talk:CPSC522/Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations/Feedback (2)

2020-04-23T15:42:43Z

TommasoDAmico: New thread: Feedback

Great page, very readable! Same as the critiques below, I cna't find the links to the study you reference. Perhaps consider retitling your component of the work from extension, I understood the meaning after looking back at the wiki structure but was confused at first.
Do you mean Logistic regression for logic regression? I wasn't able to double check this.
Overall really nice page

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. 5 The formalism (definitions, mathematics) was well chosen to make the page easier to understand. 5 The abstract is a concise and clear summary. 5 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. 5 It is correct. 5 It was neither too short nor too long for the topic. 5 It was an appropriate unit for a page. 5 It links to appropriate other pages in the wiki. 1 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. 5 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/Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps/Feedback (3)

2020-04-23T15:32:11Z

TommasoDAmico: New thread: Feedback

Interesting topic and well written, I found it a bit confusing to read the methodology after the experiment, I think reorganizing it might help your structuring. I also strugled a bit interpreting the heat maps, perhaps plaing them next to the image used to formulate it might make it more interpretable. Overall pretty good!

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. It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic). 5 It is correct. 5 It was neither too short nor too long for the topic. 5 It was an appropriate unit for a page. 5 It links to appropriate other pages in the wiki. 5 The references and links to external pages are well chosen. 5 I would recommend this page to someone who wanted to find out about the topic. 5 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/Alternative Classifiers/Feedback (2)

2020-04-23T15:18:18Z

TommasoDAmico: New thread: Feedback

The topic is interesting and movel to explore from my understanding. Although I believe the use of language may be slightly advanced for this course, further explaining certain core concepts might help the readability of the page. Otherwise I think the page looks good, great choice.

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). 4 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. It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic). 5 It is correct. 5 It was neither too short nor too long for the topic. 5 It was an appropriate unit for a page. 5 It links to appropriate other pages in the wiki. The references and links to external pages are well chosen. 5 I would recommend this page to someone who wanted to find out about the topic. 5 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

Course:CPSC522

2020-04-21T21:27:32Z

TommasoDAmico:

{{Infobox_New_Course

|title=CPSC 522 Wiki

|picture=Image:wiki.png

|subject code=CPSC

|course number=522

|instructor=David Poole

|email=poole@cs.ubc.ca

|office= 109
|office hours= after class every day
|classroom= DMP 101

}}

[[Category:CPSC522]]
Welcome to [http://www.cs.ubc.ca/~poole/cs522/2019 CPSC 522] Wiki. This is where the participants are writing the textbook. See
http://www.cs.ubc.ca/~poole/cs522/2020/ for the main web page for the course.
==The 2020 Rules==
* These rules are editable, so you can change the rules.
* [[Course:CPSC522/StudentPresentations2020|2020 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 2 students per day.
* [[Course:CPSC522/January2020|January and February Assignment]]<nowiki/>s describes your assignments for January and February.
* [[Course:CPSC522/MarchApril2020|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

==Old (2018, 2019) Rules==
*[[Course:CPSC522/StudentPresentations2018|2018 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 3 students per day.
* [[Course:CPSC522/January2018|January Assignment]] describes your assignment for January.
* [[Course:CPSC522/February2018|February Assignment]] describes your assignment for February.
* [[Course:CPSC522/MarchApril2018|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

== Guidelines ==
* Keep each page as simple as possible (but not simpler); if a page starts to get complicated, consider splitting it.
* Write pages for your peers; they should all be written for incoming graduate students, and only assume background knowledge that is common among such students.
* All pages should obey the [[Course:CPSC522/Conventions|Syntax Conventions]]. If there is a design decision that you need to make that may have non-local implications, add it to the conventions.
* It should use formalism and mathematics when (and only when) the formalism make the description clearer. Use the code tags for math, e.g., <math>P(h\mid e) = \frac{P(h\land e)}{P(e)}.</math> It is worth your while to learn [https://www.latex-project.org/ Latex] if you don't already know it.
* If there is a simple case, and a more general case, give the simple case first. Making things complicated is easy; keeping them simple is difficult and we should strive for simplicity. Any complication needs to be carefully motivated.
* Use the "discussion" tab

Each Page should contain:
* A clear jargon-free description of what is going on. Keep jargon to a minimum.
* Motivating example(s) and, where appropriate, a simple pedagogical example (which may be different from the motivating examples) that is used to explain what is going on
* An argument of plausibility
* Evidence that it works
* Code and pseudo-code, where appropriate. This code should interact with other related code (e.g., [http://aipython.org AIFCA Python Distribution]) if possible. The code should be as simple as possible to implement the techniques. Consider adding exercises as to what can be improved or made more general or bullet-proof. Use a <code>code block</code> for (pseudo-)code (even multi-line code). You can also use the format in http://wiki.ubc.ca/Course:CPSC_320/Midterm_2_Reference_Sheet#Pseudocode (try both and see which better suits your needs).

==Foundations==
Please add your page here and in the [[Course:CPSC522/Index|Index]].

* [[Course:CPSC522/MyTest|My Test]]
===General===
* [[Course:CPSC522/AGI|Artificial General Intelligence]] (2018)
* [[Course:CPSC522/Swarm_Intelligence|Swarm Intelligence]] (2018)

===Control===
* [[Course:CPSC522/Control Theory|Control Theory]] (2016)
* [[Course:CPSC522/Hierarchical Control|Hierarchical Control]] (2016)

===Probability and Graphical Models===
* [[Course:CPSC522/Probability|Probability]] (2016)
* [[Course:CPSC522/Graphical Models|Graphical Models]] (2016)
* [[Course:CPSC522/Bayesian Networks|Bayesian Networks]] (2016)
* [[Course:CPSC522/Markov_Networks|Markov Networks]] (2016)
* [[Course:CPSC522/WeightedModelCounting|Weighted Model Counting]](2019)
====Temporal Models====
* [[Course:CPSC522/Markov Chains|Markov Chains]] (2018)
* [[Course:CPSC522/Hidden_Markov_Models|Hidden Markov Models]] (2016)
* [[Course:CPSC522/Kalman_filter|Kalman filter]] (2018)
* [[Course:CPSC522/Dynamic Bayesian Networks|Dynamic Bayesian Networks]] (2018)
====Inference====
* [[Course:CPSC522/Variable Elimination|Variable Elimination]] (2016)
* [[Course:CPSC522/MCMC|Markov Chain Monte Carlo]] (2016)
* [[Course:CPSC522/Particle Filtering|Particle Filtering]] (2016)
* [[Course:CPSC522/Treatment of Missing Data|Treatment of Missing Data]] (2019)
* [[Course:CPSC522/Bayesian Coresets|Bayesian Coresets]] (2019)
* J0 [[Course:CPSC522/Variational Inference|Variational Inference]] (2020)

====Causality====
* [[Course:CPSC522/Causality|Causality]] (2016)
====Representations of Conditional Probability====
* [[Course:CPSC522/Neural Network|Neural Network]] (2016)
* [[Course:CPSC522/Recurrent Neural Networks|Recurrent Neural Networks]] (2018)
* [[Course:CPSC522/Decision_Trees|Decision Trees]] (2018)
====Learning====
* [[Course:CPSC522/Learning Probabilistic Models with Complete Data|Learning Probabilistic Models with Complete Data]] (2018)
* [[Course:CPSC522/Support_Vector_Machines|Support Vector Machines]] (2018)
* [[Course:CPSC522/Ensemble Learning|Ensemble Learning]] (2018)
* J1 [[Course:CPSC522/Principal_Component_Analysis|Principal Component Analysis (PCA)]] (2020)
* J2 [[Course:CPSC 522/Self-Organizing Maps|Self-Organizing Maps]] (2020)
* F1 [[Course:CPSC 522/Progressive Neural Network|Progressive Neural Network]] (2020)
* F5 [[Course:CPSC522/Conditional GANs for Image to Image Translation|Conditional GANs for Image-To-Image Translation]] (2020)
===NLP===
* [[Course:CPSC522/Natural Language Processing | Natural Language Processing]] (2018)
* [[Course:CPSC522/PCFG|Probabilistic Context Free Grammars]] (2018)
===Utility and Preferences===

* [[Course:CPSC522/Bounded Rationality|Bounded Rationality]] (2018)
* [[Course:CPSC522/Elicitation of Factored Utilities|Elicitation of Factored Utilities]] (2019)

===Acting Under Uncertainty===
* [[Course:CPSC522/Decision Networks|Decision Networks]] (2016)
* [[Course:CPSC522/Markov Decision Process|Markov Decision Process]] (2016)
* F0 [[Course:CPSC522/Partially Observable Markov Decision Processes|Partially Observable Markov Decision Processes]] (2020)
* [[Course:CPSC522/Reinforcement Learning|Reinforcement Learning]] (2016)
* [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning with Function Approximation]] (2016)
* [[Course:CPSC522/Game Theory|Game Theory]] (2016)
* [[Course:CPSC522/Multi-Agent Systems|Multi-Agent Systems]] (2018)
* [[Course:CPSC522/Stochastic Optimization|Stochastic Optimization]] (2018)
* [[Course:CPSC522/Value of Information and Control|Value of Information]] (2019)

===Logic===
* [[Course:CPSC522/Abduction|Abduction]] (2018)
* [[Course:CPSC522/Knowledge Compilation|Knowledge Compilation]] (2016)
* [[Course:CPSC522/Predicate Calculus|Predicate Calculus]] (2016)
* [[Course:CPSC522/Markov Logic|Markov Logic]] (2018)
* [[Course:CPSC522/Higher Order Logic|Higher Order Logic]] (2018)
* [[Course:CPSC522/Ontology|Ontology]] (2019)

==Existing Combinations (2016)==
* [[Course:CPSC522/Recommendation System using Matrix Factorization|Recommendation System using Matrix Factorization]]
* [[Course:CPSC522/Latent Dirichlet Allocation|Latent Dirichlet Allocation]]
* [[Course:CPSC522/Deep Neural Network|Deep Neural Network and Game of Go]]
* [[Course:CPSC522/Problog|Problog]]
* [[Course:CPSC522/Maximum Entropy Markov Models|Maximum Entropy Markov Models]]
* [[Course:CPSC522/Future Directions for Semantic Systems|Ontology Search Engine]]
* [[Course:CPSC522/Convolutional Neural Networks|Convolutional Neural Networks]]
* [[Course:CPSC522/Learning Markov Logic Network Structure|Learning Markov Logic Network Structure]]
* [[Course:CPSC522/Decision Support System using Interactive Preference Elicitation|Decision Support System using Interactive Preference Elicitation]]
* [[Course:CPSC522/Predicting Affect of User's Interaction with an Intelligent Tutoring System|Predicting Affect of User's Interaction with an Intelligent Tutoring System]]
* [[Course:CPSC522/Record Linkage and identity uncertainty|Record Linkage and identity uncertainty]]
* [[Course:CPSC522/Robot Scientist|Robot Scientist]]
* [[Course:CPSC522/Density-Based Unsupervised Learning|Density-Based Unsupervised Learning]]
* [[Course:CPSC522/Predicting Human Behavior in Normal-Form Games|Predicting Human Behavior in Normal-Form Games]]
* [[Course:CPSC522/Identity Uncertainty|Identity Uncertainty]]
* [[Course:CPSC522/Generative Adversarial Networks|Generative Adversarial Networks]]

* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
*[[Course:CPSC522/User-Adaptive Information Visualization|User-Adaptive Information Visualization]]

==Existing Combinations (2020)==
* J3 [[Course:CPSC522/Monte Carlo Localization |Pedestrian localization for Indoor Environments]] (2020)
* J4 [[Course:CPSC522/Automation of hypothesis generation and testing in science|Automation of hypothesis generation and testing in science]] (2020)
* J5 [[Course:CPSC522/Deep Q Network |Prioritized Experience Replay]] (2020)
* F2 [[Course:CPSC522/Variation Auto-Encoders |Variational Auto-Encoders]] (2020)
* F3[[Course:CPSC522/Combining_Collaborative_Filtering_with_Personal_Agents_for_Better_Recommendations | Hybrid Recommendation Systems]] (2020)
* F4 [[Course:CPSC522/Online Pattern Analysis by Evolving Self-Organizing Maps|Online Pattern Analysis by Evolving Self-organizing Maps]] (2020)

==Existing Combinations (2018)==
===Neural Networks===
* [[Course:CPSC522/Financial Forecasting using LSTM Networks |Financial Forecasting using LSTM Networks]] (2018)
* [[Course:CPSC522/Character Level Language Models using LSTM|Character Level Language Models using LSTM]] (2018)
* [[Course:CPSC522/TextSummarizationUsingMachineLearning |Text Summarization using Machine Learning]] (2018)
* [[Course:CPSC522/Password_cracking_using_PCFGs_and_Neural_Networks|Password Cracking using Probabilistic Context Free Grammars and Neural Networks]] (2018)
* [[CNNs in Image Segmentation]](2018)
* [[Course:CPSC522/Image_Classification_With_Convolutional_Neural_Networks|Image Classification With Convolutional Neural Networks]] (2018)
* [[Image Colourization using Deep Learning]](2018)
* [[Course:CPSC522/StackedGAN|Stacked Generative Adversarial Networks]] (2018)

===Reinforcement Learning===
* [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] (2018)
* [[Course:CPSC522/Deep_Reinforcement_Learning|Deep Reinforcement Learning]] (2018)
* [[Course:CPSC522/Self_Improving_Machines|Self-Improving Machines]] (2018)
* [[Course:CPSC522/Adaptive_Network_Routing_using_ACO|Adaptive Network Routing using Ant Colony Optimization]] (2018)

===Decision-theoretic Planning===
* [[Course:CPSC522/Action_Selection_for_MDPs|Action Selection for MDPs]] (2018)
* [[Course:CPSC522/Rao_Blackwellized_Particle_Filtering|Rao-Blackwellized Particle Filtering]](2018)
===Relational Reasoning===
* [[Course:CPSC522/Transfer_Learning_with_Markov_Logic|Transfer Learning with Markov Logic]] (2018)
* [[Course:CPSC522/Cognitive_Robotics|Cognitive Robotics]] (2018)
===Applications===
* [[Course:CPSC522/Affect Prediction using Eye Gaze|Affect Prediction using Eye Gaze]] (2018)
* [[Course:CPSC522/Conflict-Driven Clause Learning for the Boolean Satisfiability Problem|Conflict-Driven Clause Learning for the Boolean Satisfiability Problem]] (2018)

==Existing Combinations (2019)==
* [[Course:CPSC522/Ontology Extraction|Ontology Extraction]]
* [[Course:CPSC522/Restricted Boltzmann Machines for Collaborative Filtering|Restricted Boltzmann Machines for Collaborative Filtering]]
* [[Course:CPSC522/Minimax Regret Preference Elicitation for Risky Prospects|Minimax Regret Preference Elicitation for Risky Prospects]]
* [[Course:CPSC522/Sequential Monte Carlo samplers|Sequential Monte Carlo samplers]]
* [[Course:CPSC522/FastSLAM|FastSLAM]]
* [[Course:CPSC522/SMC for PGMs|Sequential Monte Carlo for Probabilistic Graphical Models]]

==Future combinations (2016)==
* [[Course:CPSC522/Sentiment Analysis|Sentiment Analysis: Movie Reviews]]
* [[Course:CPSC522/Collaborative Filtering|Collaborative Filtering]]
* [[Course:CPSC522/List Recommendation|List Recommendation]]
* [[Course:CPSC522/Inactive Cookie Mapping via Trail Matching|Inactive Cookie Mapping via Trail Matching]]
* [[Course:CPSC522/Improve recommendation system by integration|Improve Recommendation System by Integration]]
* [[Course:CPSC522/Identity Uncertainty in a restaurant data-set|Identity Uncertainty in a restaurant data-set]]
* [[Course:CPSC522/Regularization_for_Neural_Networks|Regularization for Neural Networks]]
* [[Course:CPSC522/Spam Detection|Spam Detection]]
* [[Course:CPSC522/Titanic: Machine Learning from Disaster|Titanic: Machine Learning from Disaster]]
* [[Course:CPSC522/Automatic Classification of Morphological Heart Arrhythmia | Automatic Classification of Morphological Heart Arrhythmia]]
* [[Course:CPSC522/Linking Sentences in Asynchronous Conversations|Linking Sentences in Asynchronous Conversations]]
* [[Course:CPSC522/Generic Aspect-based Aggregation of Sentiments|Generic Aspect-based Aggregation of Sentiments]]
* [[Course:CPSC522/Graph Based keyword extraction|Graph Based Key-corporation Extraction]]
* [[Course:CPSC522/Improving the accuracy of Affect Prediction in an Intelligent Tutoring System|Improving the accuracy of Affect Prediction in an Intelligent Tutoring System]]
* [[Course:CPSC522/Improving Human Behavior Prediction in Simultaneous-Move Games|Improving Human Behavior Prediction in Simultaneous-Move Games]]
* [[Course:CPSC522/The Automation of Disease Diagnosis|The Automation of Disease Diagnosis]]
* [[Course:CPSC522/Analyzing online dating trends with Weka|Analyzing online dating trends with Weka]]

==Future combinations (2018)==
* [[Course:CPSC522/Artificial Intelligence and Economic Theory|Artificial Intelligence and Economic Theory]]
* [[Course:CPSC522/Weak Semantic Map|Weak Semantic Map: Simplified Chinese]]
* [[Course:CPSC522/Network Agent|Datacenter Traffic as Reinforcement Learning Problem]]
* [[Course:CPSC522/Baseilne_of_RSI|A Theoretical Baseline of Recursive Self-improvement]]
* [[Course:CPSC522/Text_Summarization_for_busy_people!| Text summarization for busy people!!]]
* [[Course:CPSC522/An_evaluation_on_selecting_and_applying_Recommendation_Methods | An evaluation on selecting and applying Recommendation Methods]]
* [[Course:CPSC522/Learning User Preferences of Motion Control | Learning User Preferences of Motion Control]]
* [[Course:CPSC522/Experiments_with_Reinforcement_Learning| Experiments with Reinforcement Learning]]
* [[Course:CPSC522/A_Comparison_of_LDA_and_NMF_for_Topic_Modeling_on_Literary_Themes| A Comparison of LDA and NMF for Topic Modeling on Literary Themes]]
* [[Course:CPSC522/Analysis of hierarchical prior for Language modeling | Analysis of hierarchical prior for Language modeling]]
* [[Better_caching_using_reinforcement_learning|Better Caching using reinforcement learning]]
* [[Course:CPSC522/Evaluation_of_ACO|Evaluating Ant Colony Optimization in a simulation]]
* [[Course:CPSC522/SLAM_And_Sensor_Quality|SLAM and Sensor Quality]]
* [[Text generation with LSTM and Markov Chain]]
* [[Course:CPSC522/Topology_and_Embedding_Multi-relational_Data|Topology and Embedding Multi-relational Data]]

== Future combinations (2019) ==
* [[Course:CPSC522/Reinforcement Learning with Linear Model of Reward Corruption|Reinforcement Learning with Linear Model of Reward Corruption]]
*
* [[Course:CPSC522/Adverserial Belief Propagation|Adversarial Belief Propagation]]
*
* [[Course:CPSC522/Using Subset Information with Matrix Factorization|Using Subset Information with Matrix Factorization]]
*
* [[Course:CPSC522/Learning Attention via Active Inference|Learning Attention via Active Inference]]
* [[Course:CPSC522/Regularization as an Alternative to Negative Sampling in KGs|Regularization as an Alternative to Negative Sampling in KGs]]
== Future combinations (2020) ==
* [[Course:CPSC522/Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations|Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations]]
* M3 [[Course:CPSC522/Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps|Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps]]
* M1 [[Course:CPSC522/Alternative_Classifiers|Alternative Classifiers]] (2020)
* M0 [[Course:CPSC522/Grouped Prioritized Experience Replay (GPER)|Grouped Prioritized Experience Replay (GPER)]] (2020)
==Suggested Unclaimed Pages==
Here are some possible topics for pages. This list is not meant to limit your imagination. Some of them might be better split into multiple pages. There are many other possible topics.

When claimed, these pages should be moved from this section to the table of contents above and to the [[Course:CPSC522/Index|Index]] of existing pages. To claim a page you have to actually create it and edit it (and have your name on the page, so everyone can see who has claimed it).

* [[Course:CPSC522/Probability general semantics|Probability - general semantics]] with infinitely many variables and/or variables with infinite domains
* [[Course:CPSC522/Representations of Conditional Distributions|Representations of Conditional Distributions]]
* [[Course:CPSC522/Recursive Conditioning|Recursive Conditioning]]
* [[Course:CPSC522/Parity Methods|Parity Methods for Probabilistic Inference]]
* [[Course:CPSC522/Matrix Factorization|Matrix Factorization]]
* [[Course:CPSC522/Utility|Utility]]
* [[Course:CPSC522/Multi-Attribute Utility|Multi-Attribute Utility]]
* [[Course:CPSC522/Preference Elicitation|Preference Elicitation]]
* [[Course:CPSC522/Mechanism Design|Mechanism Design]]
* [[Course:CPSC522/Logic Programming|Logic Programming]]
* [[Course:CPSC522/Negation as Failure|Negation as Failure]]
* [[Course:CPSC522/Equality-Identity|Equality/Identity]]
* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
* [[Course:CPSC522/Ontologies|Ontologies]]
* [[Course:CPSC522/Continual Learning|Continual Learning]]

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-21T14:52:37Z

TommasoDAmico:

== Grouped Prioritized Experience Replay (GPER) ==
This page explores the concept of grouping prioritized experience replay memories to improve learning efficiency in temporal difference reinforcement learning environments.

Principal Author: Obada Alhumsi, Tommaso D’Amico

Collaborators:

== Abstract ==
Grouped Prioritized Experience Replay is a hypothetical extension of Prioritized Experience Replay where prioritization is done by grouped experiences rather than individual state action pairs. The page below explores the effectiveness of this method with respect to Q-Learning, Q-Learning with experience replay and Q-Learning with prioritized experience replay.

=== Builds on ===
Grouped Prioritized Experience Replay builds upon [https://wiki.ubc.ca/Course:CPSC522/Deep_Q_Network Prioritized Experience Replay] which in turn builds upon the concept of Experience Replay in [https://wiki.ubc.ca/Course:CPSC522/Deep_Q-Learning Temporal Difference Learning]. The algorithms will use [[Course:CPSC522/Reinforcement Learning with Function approximation|Q-Learning]] as a fundamental building block.

=== Related Pages ===
[https://wiki.ubc.ca/Course:CPSC522/Deep_Q_Network Deep-Q Networks] are used instead of Q-Learning to apply these algorithms in continuos learning environments.

Experience Replay is also tightly related to [https://en.wikipedia.org/wiki/Hippocampal_replay Hippocampal Replay] in the literature.

== Content ==

=== Introduction ===
Grouped Prioritized Experience Replay is a hypothetical extension of Prioritized Experience Replay where prioritization is done by grouped experiences rather than individual state-action pairs. The intention is to render learning more efficient by prioritizing experience replay to specific action or state groups with which the agent is most uncertain about. This extension is motivated by training excersices seen in a variety of sports, where an athlete repeatedly preforms actions in a set of similar envrionment states or performs similar actions in a set of random environment states.The former can be seen in soccer, where the grouped training excersices include training freekicks, cornerballs, counterattacks and other more complicated states that the game presents. The latter can be seen in table tennis, where the grouped training excersices include training a players forehand return( hitting the ball with the red side of the paddle) and backhand return(hitting the ball with the black side of the paddle). This project explores the effectiveness of this method with respect to Q-Learning, Q-Learning with experience replay and Q-Learning with prioritized experience replay.

=== Background ===

==== Experience Replay ====
Experience Replay is an extension of Q-learning where instead of just running Q-learning on state-action pairs as they occur, the agent stores these state-actions pair experiences and updates them based on future experiences that occur, essentially introducing the concept of memory to the algorithm. This way the algorithm has more efficient use of its experiences and is able to learn faster than standard Q-learning.

==== Prioritized Experience Replay ====
Prioritized Experience Replay attempts to optimize Experience Replay to areas where the agent is more uncertain of its actions by prioritizing experiences with a high temporal-difference error (with some stochastic elements). This allows the agent to learn more quickly by avoiding going over experiences it has mastered and focusing on the ones where it seems to be making more mistakes. By doing so Prioritized experience replay allows for more valuable memory storage as only relevant experiences remain stored and are replayed. For more detailed information on this topic visit the page on Deep-Q Networks.

=== Hypothesis ===
The hypothesis to be tested is that the concept of grouping priorities in experience replay by state or action can improve training efficiency and minimize error for temporal difference learning algorithms in comparison to plain Q-Learning, Q-Learning with Experience Replay and Q-Learning with Prioritized Experience Replay.

=== Algorithm ===
Grouped Prioritized Experience Replay is a type of prioritization focused on groups rather than individual experiences. In order to acomplish group prioritization, after each time step, the memory of the last experience is stored according to its groupping. The TD Error of all stored experiences are then calculated and each group average TD error is obtained. The group with the highest average TD error is then sampled from at uniform.

For example, if grouping is done by action, after a certain time step, if the agent moved up, the resulting experience will be placed under the action group "move up". The error of each experience is then calculated and averaged for each group. It may be that the agent is most uncertain of movements to the left, therefore those experiences will be replayed, ideally improving its performance "going left" more quickly.
[[File:GPER_Pseudo-code.png|center|thumb|463x463px|Simple implementation of the GPER sampling algorithm]]

=== Testing ===
[[File:Taxi-v3.png|thumb|Taxi-v3 Game Environment Render]]

==== Test Environment ====
The testing for this algorithm was done using a modified version of the [https://gym.openai.com/envs/Taxi-v3/ Taxi-v3 game] environment present in the [https://gym.openai.com/envs/#toy_text OpenAi Gym Library].
[[File:Taxi-v3 full.png|thumb|Taxi-v3 Game with Passenger inside Taxi]]
In the original Taxi-v3 game and in the modified version the taxi starts off at a random square and the passenger is at a random location. The taxi drives to the passenger's location, picks up the passenger, drives to the passenger's destination and then drops off the passenger. Once the passenger is dropped off, the episode ends.

The following are the labels demonstrated in the render of the game:
* letters and numbers (R, G, B, Y, 0-7): locations for passenger and destinations
* blue: passenger
* magenta: destination
* yellow: empty taxi
* green: full taxi
[[File:Taxi mod big.png|thumb|Modified Taxi-v3 game environment]]
The modified version of the game is an extention of the map and an increase in locations and destinations for the passanger. This was done in an effort to obtain a larger discrete environment to train the algorithms on to more suitably display the differences in training efficiency.

The original Taxi-v3 game has 500 states (5 x-axis positions, 5 y-axis positions, 4 destination locations and 5 passanger locations) and 6 actions (move up, move down, move left, move right, pickup passenger and dropoff passenger).

The Modified Taxi game has 28800 states (20 x-axis positions, 20 y-axis positions, 8 destination locations and 9 passanger locations) and the same 6 actions as the original.

Rewards in the modified Taxi game were given as follows:
* -1 for movement
* -1 for wrong dropoff or pickup
* +100 for successful dropoff

==== Methodology ====
In order to test the performance of Grouped Prioritized Experience Replay a set of algorithms was used as baseline for performance. Since GPER builds upon other concepts the following algorithms were used in comparison:
* Q-Learning
* Q-Learning with Experience Replay
* Q-Learning with Proportional Prioritized Experience Replay
* Q-Learning with Rank-Based Prioritized Experience Replay
* Q-Learning with GPER action grouping (6 groups)
* Q-Learning with GPER x-y position state grouping (4 groups, each group makes a quadrant of the grid)
* Q-Learning with GPER destination location grouping (8 groups)
* Q-Learning with GPER passenger location grouping (9 groups)
All algorithms were trained with the same parameters and environment to avoid biases.

==== Results ====
For the results below the algorithms have played through 40000 games of Modified Taxi-v3 with a limit of 900 turns per game.

The following plot represent the reward obtained by the agent at each episode averaged every 100 episodes for each algorithm tested.
[[File:Grouped Prioritized Experience Replay Reward Plot.png|center|thumb|1183x1183px|Average Rewards over 40000 episodes for each algorithm]]
The following plot is a zoomed in version of the prior to demonstrate more closely the performance of each algorithm when converging.
[[File:Zoomed in Grouped Prioritized Experience Replay Reward Plot.png|center|thumb|1180x1180px|Zoomed in view of reward plot]]
The following plot demonstrates the average episode length for each algorithm over time.
[[File:Grouped Prioritized Experience Replay Episode Length Plot.png|center|thumb|1185x1185px|Average episode legth over time (max episode length: 900)]]

=== Discussion ===
In the average reward plot it can be seen that although all algorithms seem to converge, some converge at lower scores than others. This is mainly due to the averaging effect used to clean up the data for visualization. most algorithms seem to have reached the maximum highscores although those illustrated with lower averages tended to be more erratic in behaviour, meaning that the variance in the performance appeared much larger. It is possible that with further training these would eventually converge to the global maximum although it appears that some have settled in local maxima, such as Experience Replay.

It can be seen also that none of the GPER methods tested achieved the same performance as prior established algorithms.

From the last plot illustrating episode length over time,the tested GPER algorithms never quite learned the game, appearing to not complete most times. For example in Passenger Location GPER the agent seems to run out of steps about 3 out of 4 times it attempts the game. This may be as the passenger location grouping is only relevant to the game for the first component where the agent needs to find the passenger.

The best performing GPER grouping tested seemed to be grouping by XY Taxi coordinates, where the grid is divided into 4 quadrants/groups. Unlike passenger location and destination location grouping, XY grouping is useful throughout the entire game, which could have lead to its increased performance. However, action groupings, which are useful throughout the game as well, did not perform as well. This leads to the idea that state grouping could generally be better than action grouping, nonetheless, further testing on different environment and parameter fine tuning should be performed before coming to such a conclusion. It is interesting to notice that initially XY Taxi Location GPER also seems to outperform the established algorithms. This may be because of the desired effect of grouping seeked by this experiment, where by grouping experiences by relevant states, the algorithm restricts prioritization only to groups considered relevant by the designer, reducing the need for the algorithm to train against redundant behaviours.

Overall GPER does not seem to be a better algorithm than currently used algorithms for experience replay in Q-Learning. It does although seems to provide valuable insights to which state types may be relevant for the learning task. From the graphs above there is a clear difference in performance for each grouping which suggests a difference in relevance of each state type to the learning process. This may be relevant to understanding what influences the learning process of an agent over time.

== Annotated Bibliography ==

== To Add ==

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-20T20:23:04Z

TommasoDAmico:

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-20T20:22:42Z

TommasoDAmico:

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-20T20:21:58Z

TommasoDAmico:

File:Grouped Prioritized Experience Replay Episode Length Plot.png

2020-04-20T18:53:39Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Plot comparing Grouped Prioritized Experience Replay with other Learning Algorithms based on episode training length over 40000 episodes of modified version of Taxi-v3 OpenAi Gym Game Environment.
Maximum training length was 900 episodes.}}
|date=2020-04-20
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

File:Zoomed in Grouped Prioritized Experience Replay Reward Plot.png

2020-04-20T18:53:39Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Zoome in version of plot comparing Grouped Prioritized Experience Replay with other Learning Algorithms based on rewards over 40000 episodes of modified version of Taxi-v3 OpenAi Gym Game Environment.}}
|date=2020-04-20
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

File:Grouped Prioritized Experience Replay Reward Plot.png

2020-04-20T18:53:39Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Plot comparing Grouped Prioritized Experience Replay with other Learning Algorithms based on rewards over 40000 episodes of modified version of Taxi-v3 OpenAi Gym Game Environment.}}
|date=2020-04-20
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-19T23:24:35Z

TommasoDAmico:

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-19T23:23:55Z

TommasoDAmico:

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-19T23:17:02Z

TommasoDAmico:

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-19T22:37:41Z

TommasoDAmico:

Course:CPSC522

2020-04-19T22:36:55Z

TommasoDAmico:

{{Infobox_New_Course

|title=CPSC 522 Wiki

|picture=Image:wiki.png

|subject code=CPSC

|course number=522

|instructor=David Poole

|email=poole@cs.ubc.ca

|office= 109
|office hours= after class every day
|classroom= DMP 101

}}

[[Category:CPSC522]]
Welcome to [http://www.cs.ubc.ca/~poole/cs522/2019 CPSC 522] Wiki. This is where the participants are writing the textbook. See
http://www.cs.ubc.ca/~poole/cs522/2020/ for the main web page for the course.
==The 2020 Rules==
* These rules are editable, so you can change the rules.
* [[Course:CPSC522/StudentPresentations2020|2020 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 2 students per day.
* [[Course:CPSC522/January2020|January and February Assignment]]<nowiki/>s describes your assignments for January and February.
* [[Course:CPSC522/MarchApril2020|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

==Old (2018, 2019) Rules==
*[[Course:CPSC522/StudentPresentations2018|2018 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 3 students per day.
* [[Course:CPSC522/January2018|January Assignment]] describes your assignment for January.
* [[Course:CPSC522/February2018|February Assignment]] describes your assignment for February.
* [[Course:CPSC522/MarchApril2018|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

== Guidelines ==
* Keep each page as simple as possible (but not simpler); if a page starts to get complicated, consider splitting it.
* Write pages for your peers; they should all be written for incoming graduate students, and only assume background knowledge that is common among such students.
* All pages should obey the [[Course:CPSC522/Conventions|Syntax Conventions]]. If there is a design decision that you need to make that may have non-local implications, add it to the conventions.
* It should use formalism and mathematics when (and only when) the formalism make the description clearer. Use the code tags for math, e.g., <math>P(h\mid e) = \frac{P(h\land e)}{P(e)}.</math> It is worth your while to learn [https://www.latex-project.org/ Latex] if you don't already know it.
* If there is a simple case, and a more general case, give the simple case first. Making things complicated is easy; keeping them simple is difficult and we should strive for simplicity. Any complication needs to be carefully motivated.
* Use the "discussion" tab

Each Page should contain:
* A clear jargon-free description of what is going on. Keep jargon to a minimum.
* Motivating example(s) and, where appropriate, a simple pedagogical example (which may be different from the motivating examples) that is used to explain what is going on
* An argument of plausibility
* Evidence that it works
* Code and pseudo-code, where appropriate. This code should interact with other related code (e.g., [http://aipython.org AIFCA Python Distribution]) if possible. The code should be as simple as possible to implement the techniques. Consider adding exercises as to what can be improved or made more general or bullet-proof. Use a <code>code block</code> for (pseudo-)code (even multi-line code). You can also use the format in http://wiki.ubc.ca/Course:CPSC_320/Midterm_2_Reference_Sheet#Pseudocode (try both and see which better suits your needs).

==Foundations==
Please add your page here and in the [[Course:CPSC522/Index|Index]].

* [[Course:CPSC522/MyTest|My Test]]
===General===
* [[Course:CPSC522/AGI|Artificial General Intelligence]] (2018)
* [[Course:CPSC522/Swarm_Intelligence|Swarm Intelligence]] (2018)

===Control===
* [[Course:CPSC522/Control Theory|Control Theory]] (2016)
* [[Course:CPSC522/Hierarchical Control|Hierarchical Control]] (2016)

===Probability and Graphical Models===
* [[Course:CPSC522/Probability|Probability]] (2016)
* [[Course:CPSC522/Graphical Models|Graphical Models]] (2016)
* [[Course:CPSC522/Bayesian Networks|Bayesian Networks]] (2016)
* [[Course:CPSC522/Markov_Networks|Markov Networks]] (2016)
* [[Course:CPSC522/WeightedModelCounting|Weighted Model Counting]](2019)
====Temporal Models====
* [[Course:CPSC522/Markov Chains|Markov Chains]] (2018)
* [[Course:CPSC522/Hidden_Markov_Models|Hidden Markov Models]] (2016)
* [[Course:CPSC522/Kalman_filter|Kalman filter]] (2018)
* [[Course:CPSC522/Dynamic Bayesian Networks|Dynamic Bayesian Networks]] (2018)
====Inference====
* [[Course:CPSC522/Variable Elimination|Variable Elimination]] (2016)
* [[Course:CPSC522/MCMC|Markov Chain Monte Carlo]] (2016)
* [[Course:CPSC522/Particle Filtering|Particle Filtering]] (2016)
* [[Course:CPSC522/Treatment of Missing Data|Treatment of Missing Data]] (2019)
* [[Course:CPSC522/Bayesian Coresets|Bayesian Coresets]] (2019)
* J0 [[Course:CPSC522/Variational Inference|Variational Inference]] (2020)

====Causality====
* [[Course:CPSC522/Causality|Causality]] (2016)
====Representations of Conditional Probability====
* [[Course:CPSC522/Neural Network|Neural Network]] (2016)
* [[Course:CPSC522/Recurrent Neural Networks|Recurrent Neural Networks]] (2018)
* [[Course:CPSC522/Decision_Trees|Decision Trees]] (2018)
====Learning====
* [[Course:CPSC522/Learning Probabilistic Models with Complete Data|Learning Probabilistic Models with Complete Data]] (2018)
* [[Course:CPSC522/Support_Vector_Machines|Support Vector Machines]] (2018)
* [[Course:CPSC522/Ensemble Learning|Ensemble Learning]] (2018)
* J1 [[Course:CPSC522/Principal_Component_Analysis|Principal Component Analysis (PCA)]] (2020)
* J2 [[Course:CPSC 522/Self-Organizing Maps|Self-Organizing Maps]] (2020)
* F1 [[Course:CPSC 522/Progressive Neural Network|Progressive Neural Network]] (2020)
* F5 [[Course:CPSC522/Conditional GANs for Image to Image Translation|Conditional GANs for Image-To-Image Translation]] (2020)
* Term Project: [[Course:CPSC522/Alternative_Classifiers|Alternative Classifiers]] (2020)
* M0 [[Course:CPSC522/Grouped Prioritized Experience Replay (GPER)|Grouped Prioritized Experience Replay (GPER)]] (2020)
===NLP===
* [[Course:CPSC522/Natural Language Processing | Natural Language Processing]] (2018)
* [[Course:CPSC522/PCFG|Probabilistic Context Free Grammars]] (2018)
===Utility and Preferences===

* [[Course:CPSC522/Bounded Rationality|Bounded Rationality]] (2018)
* [[Course:CPSC522/Elicitation of Factored Utilities|Elicitation of Factored Utilities]] (2019)

===Acting Under Uncertainty===
* [[Course:CPSC522/Decision Networks|Decision Networks]] (2016)
* [[Course:CPSC522/Markov Decision Process|Markov Decision Process]] (2016)
* F0 [[Course:CPSC522/Partially Observable Markov Decision Processes|Partially Observable Markov Decision Processes]] (2020)
* [[Course:CPSC522/Reinforcement Learning|Reinforcement Learning]] (2016)
* [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning with Function Approximation]] (2016)
* [[Course:CPSC522/Game Theory|Game Theory]] (2016)
* [[Course:CPSC522/Multi-Agent Systems|Multi-Agent Systems]] (2018)
* [[Course:CPSC522/Stochastic Optimization|Stochastic Optimization]] (2018)
* [[Course:CPSC522/Value of Information and Control|Value of Information]] (2019)

===Logic===
* [[Course:CPSC522/Abduction|Abduction]] (2018)
* [[Course:CPSC522/Knowledge Compilation|Knowledge Compilation]] (2016)
* [[Course:CPSC522/Predicate Calculus|Predicate Calculus]] (2016)
* [[Course:CPSC522/Markov Logic|Markov Logic]] (2018)
* [[Course:CPSC522/Higher Order Logic|Higher Order Logic]] (2018)
* [[Course:CPSC522/Ontology|Ontology]] (2019)

==Existing Combinations (2016)==
* [[Course:CPSC522/Recommendation System using Matrix Factorization|Recommendation System using Matrix Factorization]]
* [[Course:CPSC522/Latent Dirichlet Allocation|Latent Dirichlet Allocation]]
* [[Course:CPSC522/Deep Neural Network|Deep Neural Network and Game of Go]]
* [[Course:CPSC522/Problog|Problog]]
* [[Course:CPSC522/Maximum Entropy Markov Models|Maximum Entropy Markov Models]]
* [[Course:CPSC522/Future Directions for Semantic Systems|Ontology Search Engine]]
* [[Course:CPSC522/Convolutional Neural Networks|Convolutional Neural Networks]]
* [[Course:CPSC522/Learning Markov Logic Network Structure|Learning Markov Logic Network Structure]]
* [[Course:CPSC522/Decision Support System using Interactive Preference Elicitation|Decision Support System using Interactive Preference Elicitation]]
* [[Course:CPSC522/Predicting Affect of User's Interaction with an Intelligent Tutoring System|Predicting Affect of User's Interaction with an Intelligent Tutoring System]]
* [[Course:CPSC522/Record Linkage and identity uncertainty|Record Linkage and identity uncertainty]]
* [[Course:CPSC522/Robot Scientist|Robot Scientist]]
* [[Course:CPSC522/Density-Based Unsupervised Learning|Density-Based Unsupervised Learning]]
* [[Course:CPSC522/Predicting Human Behavior in Normal-Form Games|Predicting Human Behavior in Normal-Form Games]]
* [[Course:CPSC522/Identity Uncertainty|Identity Uncertainty]]
* [[Course:CPSC522/Generative Adversarial Networks|Generative Adversarial Networks]]

* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
*[[Course:CPSC522/User-Adaptive Information Visualization|User-Adaptive Information Visualization]]

==Existing Combinations (2020)==
* J3 [[Course:CPSC522/Monte Carlo Localization |Pedestrian localization for Indoor Environments]] (2020)
* J4 [[Course:CPSC522/Automation of hypothesis generation and testing in science|Automation of hypothesis generation and testing in science]] (2020)
* J5 [[Course:CPSC522/Deep Q Network |Prioritized Experience Replay]] (2020)
* F2 [[Course:CPSC522/Variation Auto-Encoders |Variational Auto-Encoders]] (2020)
* F3[[Course:CPSC522/Combining_Collaborative_Filtering_with_Personal_Agents_for_Better_Recommendations | Hybrid Recommendation Systems]] (2020)
* F4 [[Course:CPSC522/Online Pattern Analysis by Evolving Self-Organizing Maps|Online Pattern Analysis by Evolving Self-organizing Maps]] (2020)

==Existing Combinations (2018)==
===Neural Networks===
* [[Course:CPSC522/Financial Forecasting using LSTM Networks |Financial Forecasting using LSTM Networks]] (2018)
* [[Course:CPSC522/Character Level Language Models using LSTM|Character Level Language Models using LSTM]] (2018)
* [[Course:CPSC522/TextSummarizationUsingMachineLearning |Text Summarization using Machine Learning]] (2018)
* [[Course:CPSC522/Password_cracking_using_PCFGs_and_Neural_Networks|Password Cracking using Probabilistic Context Free Grammars and Neural Networks]] (2018)
* [[CNNs in Image Segmentation]](2018)
* [[Course:CPSC522/Image_Classification_With_Convolutional_Neural_Networks|Image Classification With Convolutional Neural Networks]] (2018)
* [[Image Colourization using Deep Learning]](2018)
* [[Course:CPSC522/StackedGAN|Stacked Generative Adversarial Networks]] (2018)

===Reinforcement Learning===
* [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] (2018)
* [[Course:CPSC522/Deep_Reinforcement_Learning|Deep Reinforcement Learning]] (2018)
* [[Course:CPSC522/Self_Improving_Machines|Self-Improving Machines]] (2018)
* [[Course:CPSC522/Adaptive_Network_Routing_using_ACO|Adaptive Network Routing using Ant Colony Optimization]] (2018)

===Decision-theoretic Planning===
* [[Course:CPSC522/Action_Selection_for_MDPs|Action Selection for MDPs]] (2018)
* [[Course:CPSC522/Rao_Blackwellized_Particle_Filtering|Rao-Blackwellized Particle Filtering]](2018)
===Relational Reasoning===
* [[Course:CPSC522/Transfer_Learning_with_Markov_Logic|Transfer Learning with Markov Logic]] (2018)
* [[Course:CPSC522/Cognitive_Robotics|Cognitive Robotics]] (2018)
===Applications===
* [[Course:CPSC522/Affect Prediction using Eye Gaze|Affect Prediction using Eye Gaze]] (2018)
* [[Course:CPSC522/Conflict-Driven Clause Learning for the Boolean Satisfiability Problem|Conflict-Driven Clause Learning for the Boolean Satisfiability Problem]] (2018)

==Existing Combinations (2019)==
* [[Course:CPSC522/Ontology Extraction|Ontology Extraction]]
* [[Course:CPSC522/Restricted Boltzmann Machines for Collaborative Filtering|Restricted Boltzmann Machines for Collaborative Filtering]]
* [[Course:CPSC522/Minimax Regret Preference Elicitation for Risky Prospects|Minimax Regret Preference Elicitation for Risky Prospects]]
* [[Course:CPSC522/Sequential Monte Carlo samplers|Sequential Monte Carlo samplers]]
* [[Course:CPSC522/FastSLAM|FastSLAM]]
* [[Course:CPSC522/SMC for PGMs|Sequential Monte Carlo for Probabilistic Graphical Models]]

==Future combinations (2016)==
* [[Course:CPSC522/Sentiment Analysis|Sentiment Analysis: Movie Reviews]]
* [[Course:CPSC522/Collaborative Filtering|Collaborative Filtering]]
* [[Course:CPSC522/List Recommendation|List Recommendation]]
* [[Course:CPSC522/Inactive Cookie Mapping via Trail Matching|Inactive Cookie Mapping via Trail Matching]]
* [[Course:CPSC522/Improve recommendation system by integration|Improve Recommendation System by Integration]]
* [[Course:CPSC522/Identity Uncertainty in a restaurant data-set|Identity Uncertainty in a restaurant data-set]]
* [[Course:CPSC522/Regularization_for_Neural_Networks|Regularization for Neural Networks]]
* [[Course:CPSC522/Spam Detection|Spam Detection]]
* [[Course:CPSC522/Titanic: Machine Learning from Disaster|Titanic: Machine Learning from Disaster]]
* [[Course:CPSC522/Automatic Classification of Morphological Heart Arrhythmia | Automatic Classification of Morphological Heart Arrhythmia]]
* [[Course:CPSC522/Linking Sentences in Asynchronous Conversations|Linking Sentences in Asynchronous Conversations]]
* [[Course:CPSC522/Generic Aspect-based Aggregation of Sentiments|Generic Aspect-based Aggregation of Sentiments]]
* [[Course:CPSC522/Graph Based keyword extraction|Graph Based Key-corporation Extraction]]
* [[Course:CPSC522/Improving the accuracy of Affect Prediction in an Intelligent Tutoring System|Improving the accuracy of Affect Prediction in an Intelligent Tutoring System]]
* [[Course:CPSC522/Improving Human Behavior Prediction in Simultaneous-Move Games|Improving Human Behavior Prediction in Simultaneous-Move Games]]
* [[Course:CPSC522/The Automation of Disease Diagnosis|The Automation of Disease Diagnosis]]
* [[Course:CPSC522/Analyzing online dating trends with Weka|Analyzing online dating trends with Weka]]

==Future combinations (2018)==
* [[Course:CPSC522/Artificial Intelligence and Economic Theory|Artificial Intelligence and Economic Theory]]
* [[Course:CPSC522/Weak Semantic Map|Weak Semantic Map: Simplified Chinese]]
* [[Course:CPSC522/Network Agent|Datacenter Traffic as Reinforcement Learning Problem]]
* [[Course:CPSC522/Baseilne_of_RSI|A Theoretical Baseline of Recursive Self-improvement]]
* [[Course:CPSC522/Text_Summarization_for_busy_people!| Text summarization for busy people!!]]
* [[Course:CPSC522/An_evaluation_on_selecting_and_applying_Recommendation_Methods | An evaluation on selecting and applying Recommendation Methods]]
* [[Course:CPSC522/Learning User Preferences of Motion Control | Learning User Preferences of Motion Control]]
* [[Course:CPSC522/Experiments_with_Reinforcement_Learning| Experiments with Reinforcement Learning]]
* [[Course:CPSC522/A_Comparison_of_LDA_and_NMF_for_Topic_Modeling_on_Literary_Themes| A Comparison of LDA and NMF for Topic Modeling on Literary Themes]]
* [[Course:CPSC522/Analysis of hierarchical prior for Language modeling | Analysis of hierarchical prior for Language modeling]]
* [[Better_caching_using_reinforcement_learning|Better Caching using reinforcement learning]]
* [[Course:CPSC522/Evaluation_of_ACO|Evaluating Ant Colony Optimization in a simulation]]
* [[Course:CPSC522/SLAM_And_Sensor_Quality|SLAM and Sensor Quality]]
* [[Text generation with LSTM and Markov Chain]]
* [[Course:CPSC522/Topology_and_Embedding_Multi-relational_Data|Topology and Embedding Multi-relational Data]]

== Future combinations (2019) ==
* [[Course:CPSC522/Reinforcement Learning with Linear Model of Reward Corruption|Reinforcement Learning with Linear Model of Reward Corruption]]
*
* [[Course:CPSC522/Adverserial Belief Propagation|Adversarial Belief Propagation]]
*
* [[Course:CPSC522/Using Subset Information with Matrix Factorization|Using Subset Information with Matrix Factorization]]
*
* [[Course:CPSC522/Learning Attention via Active Inference|Learning Attention via Active Inference]]
* [[Course:CPSC522/Regularization as an Alternative to Negative Sampling in KGs|Regularization as an Alternative to Negative Sampling in KGs]]
== Future combinations (2020) ==
* [[Course:CPSC522/Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations|Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations]]
* [[Course:CPSC522/Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps|Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps]]
==Suggested Unclaimed Pages==
Here are some possible topics for pages. This list is not meant to limit your imagination. Some of them might be better split into multiple pages. There are many other possible topics.

When claimed, these pages should be moved from this section to the table of contents above and to the [[Course:CPSC522/Index|Index]] of existing pages. To claim a page you have to actually create it and edit it (and have your name on the page, so everyone can see who has claimed it).

* [[Course:CPSC522/Probability general semantics|Probability - general semantics]] with infinitely many variables and/or variables with infinite domains
* [[Course:CPSC522/Representations of Conditional Distributions|Representations of Conditional Distributions]]
* [[Course:CPSC522/Recursive Conditioning|Recursive Conditioning]]
* [[Course:CPSC522/Parity Methods|Parity Methods for Probabilistic Inference]]
* [[Course:CPSC522/Matrix Factorization|Matrix Factorization]]
* [[Course:CPSC522/Utility|Utility]]
* [[Course:CPSC522/Multi-Attribute Utility|Multi-Attribute Utility]]
* [[Course:CPSC522/Preference Elicitation|Preference Elicitation]]
* [[Course:CPSC522/Mechanism Design|Mechanism Design]]
* [[Course:CPSC522/Logic Programming|Logic Programming]]
* [[Course:CPSC522/Negation as Failure|Negation as Failure]]
* [[Course:CPSC522/Equality-Identity|Equality/Identity]]
* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
* [[Course:CPSC522/Ontologies|Ontologies]]
* [[Course:CPSC522/Continual Learning|Continual Learning]]

Course:CPSC522

2020-04-19T22:23:16Z

TommasoDAmico:

{{Infobox_New_Course

|title=CPSC 522 Wiki

|picture=Image:wiki.png

|subject code=CPSC

|course number=522

|instructor=David Poole

|email=poole@cs.ubc.ca

|office= 109
|office hours= after class every day
|classroom= DMP 101

}}

[[Category:CPSC522]]
Welcome to [http://www.cs.ubc.ca/~poole/cs522/2019 CPSC 522] Wiki. This is where the participants are writing the textbook. See
http://www.cs.ubc.ca/~poole/cs522/2020/ for the main web page for the course.
==The 2020 Rules==
* These rules are editable, so you can change the rules.
* [[Course:CPSC522/StudentPresentations2020|2020 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 2 students per day.
* [[Course:CPSC522/January2020|January and February Assignment]]<nowiki/>s describes your assignments for January and February.
* [[Course:CPSC522/MarchApril2020|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

==Old (2018, 2019) Rules==
*[[Course:CPSC522/StudentPresentations2018|2018 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 3 students per day.
* [[Course:CPSC522/January2018|January Assignment]] describes your assignment for January.
* [[Course:CPSC522/February2018|February Assignment]] describes your assignment for February.
* [[Course:CPSC522/MarchApril2018|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

== Guidelines ==
* Keep each page as simple as possible (but not simpler); if a page starts to get complicated, consider splitting it.
* Write pages for your peers; they should all be written for incoming graduate students, and only assume background knowledge that is common among such students.
* All pages should obey the [[Course:CPSC522/Conventions|Syntax Conventions]]. If there is a design decision that you need to make that may have non-local implications, add it to the conventions.
* It should use formalism and mathematics when (and only when) the formalism make the description clearer. Use the code tags for math, e.g., <math>P(h\mid e) = \frac{P(h\land e)}{P(e)}.</math> It is worth your while to learn [https://www.latex-project.org/ Latex] if you don't already know it.
* If there is a simple case, and a more general case, give the simple case first. Making things complicated is easy; keeping them simple is difficult and we should strive for simplicity. Any complication needs to be carefully motivated.
* Use the "discussion" tab

Each Page should contain:
* A clear jargon-free description of what is going on. Keep jargon to a minimum.
* Motivating example(s) and, where appropriate, a simple pedagogical example (which may be different from the motivating examples) that is used to explain what is going on
* An argument of plausibility
* Evidence that it works
* Code and pseudo-code, where appropriate. This code should interact with other related code (e.g., [http://aipython.org AIFCA Python Distribution]) if possible. The code should be as simple as possible to implement the techniques. Consider adding exercises as to what can be improved or made more general or bullet-proof. Use a <code>code block</code> for (pseudo-)code (even multi-line code). You can also use the format in http://wiki.ubc.ca/Course:CPSC_320/Midterm_2_Reference_Sheet#Pseudocode (try both and see which better suits your needs).

==Foundations==
Please add your page here and in the [[Course:CPSC522/Index|Index]].

* [[Course:CPSC522/MyTest|My Test]]
===General===
* [[Course:CPSC522/AGI|Artificial General Intelligence]] (2018)
* [[Course:CPSC522/Swarm_Intelligence|Swarm Intelligence]] (2018)

===Control===
* [[Course:CPSC522/Control Theory|Control Theory]] (2016)
* [[Course:CPSC522/Hierarchical Control|Hierarchical Control]] (2016)

===Probability and Graphical Models===
* [[Course:CPSC522/Probability|Probability]] (2016)
* [[Course:CPSC522/Graphical Models|Graphical Models]] (2016)
* [[Course:CPSC522/Bayesian Networks|Bayesian Networks]] (2016)
* [[Course:CPSC522/Markov_Networks|Markov Networks]] (2016)
* [[Course:CPSC522/WeightedModelCounting|Weighted Model Counting]](2019)
====Temporal Models====
* [[Course:CPSC522/Markov Chains|Markov Chains]] (2018)
* [[Course:CPSC522/Hidden_Markov_Models|Hidden Markov Models]] (2016)
* [[Course:CPSC522/Kalman_filter|Kalman filter]] (2018)
* [[Course:CPSC522/Dynamic Bayesian Networks|Dynamic Bayesian Networks]] (2018)
====Inference====
* [[Course:CPSC522/Variable Elimination|Variable Elimination]] (2016)
* [[Course:CPSC522/MCMC|Markov Chain Monte Carlo]] (2016)
* [[Course:CPSC522/Particle Filtering|Particle Filtering]] (2016)
* [[Course:CPSC522/Treatment of Missing Data|Treatment of Missing Data]] (2019)
* [[Course:CPSC522/Bayesian Coresets|Bayesian Coresets]] (2019)
* J0 [[Course:CPSC522/Variational Inference|Variational Inference]] (2020)

====Causality====
* [[Course:CPSC522/Causality|Causality]] (2016)
====Representations of Conditional Probability====
* [[Course:CPSC522/Neural Network|Neural Network]] (2016)
* [[Course:CPSC522/Recurrent Neural Networks|Recurrent Neural Networks]] (2018)
* [[Course:CPSC522/Decision_Trees|Decision Trees]] (2018)
====Learning====
* [[Course:CPSC522/Learning Probabilistic Models with Complete Data|Learning Probabilistic Models with Complete Data]] (2018)
* [[Course:CPSC522/Support_Vector_Machines|Support Vector Machines]] (2018)
* [[Course:CPSC522/Ensemble Learning|Ensemble Learning]] (2018)
* J1 [[Course:CPSC522/Principal_Component_Analysis|Principal Component Analysis (PCA)]] (2020)
* J2 [[Course:CPSC 522/Self-Organizing Maps|Self-Organizing Maps]] (2020)
* F1 [[Course:CPSC 522/Progressive Neural Network|Progressive Neural Network]] (2020)
* F5 [[Course:CPSC522/Conditional GANs for Image to Image Translation|Conditional GANs for Image-To-Image Translation]] (2020)
* Term Project: [[Course:CPSC522/Alternative_Classifiers|Alternative Classifiers]] (2020)
===NLP===
* [[Course:CPSC522/Natural Language Processing | Natural Language Processing]] (2018)
* [[Course:CPSC522/PCFG|Probabilistic Context Free Grammars]] (2018)
===Utility and Preferences===

* [[Course:CPSC522/Bounded Rationality|Bounded Rationality]] (2018)
* [[Course:CPSC522/Elicitation of Factored Utilities|Elicitation of Factored Utilities]] (2019)

===Acting Under Uncertainty===
* [[Course:CPSC522/Decision Networks|Decision Networks]] (2016)
* [[Course:CPSC522/Markov Decision Process|Markov Decision Process]] (2016)
* F0 [[Course:CPSC522/Partially Observable Markov Decision Processes|Partially Observable Markov Decision Processes]] (2020)
* [[Course:CPSC522/Reinforcement Learning|Reinforcement Learning]] (2016)
* [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning with Function Approximation]] (2016)
* [[Course:CPSC522/Game Theory|Game Theory]] (2016)
* [[Course:CPSC522/Multi-Agent Systems|Multi-Agent Systems]] (2018)
* [[Course:CPSC522/Stochastic Optimization|Stochastic Optimization]] (2018)
* [[Course:CPSC522/Value of Information and Control|Value of Information]] (2019)

===Logic===
* [[Course:CPSC522/Abduction|Abduction]] (2018)
* [[Course:CPSC522/Knowledge Compilation|Knowledge Compilation]] (2016)
* [[Course:CPSC522/Predicate Calculus|Predicate Calculus]] (2016)
* [[Course:CPSC522/Markov Logic|Markov Logic]] (2018)
* [[Course:CPSC522/Higher Order Logic|Higher Order Logic]] (2018)
* [[Course:CPSC522/Ontology|Ontology]] (2019)

==Existing Combinations (2016)==
* [[Course:CPSC522/Recommendation System using Matrix Factorization|Recommendation System using Matrix Factorization]]
* [[Course:CPSC522/Latent Dirichlet Allocation|Latent Dirichlet Allocation]]
* [[Course:CPSC522/Deep Neural Network|Deep Neural Network and Game of Go]]
* [[Course:CPSC522/Problog|Problog]]
* [[Course:CPSC522/Maximum Entropy Markov Models|Maximum Entropy Markov Models]]
* [[Course:CPSC522/Future Directions for Semantic Systems|Ontology Search Engine]]
* [[Course:CPSC522/Convolutional Neural Networks|Convolutional Neural Networks]]
* [[Course:CPSC522/Learning Markov Logic Network Structure|Learning Markov Logic Network Structure]]
* [[Course:CPSC522/Decision Support System using Interactive Preference Elicitation|Decision Support System using Interactive Preference Elicitation]]
* [[Course:CPSC522/Predicting Affect of User's Interaction with an Intelligent Tutoring System|Predicting Affect of User's Interaction with an Intelligent Tutoring System]]
* [[Course:CPSC522/Record Linkage and identity uncertainty|Record Linkage and identity uncertainty]]
* [[Course:CPSC522/Robot Scientist|Robot Scientist]]
* [[Course:CPSC522/Density-Based Unsupervised Learning|Density-Based Unsupervised Learning]]
* [[Course:CPSC522/Predicting Human Behavior in Normal-Form Games|Predicting Human Behavior in Normal-Form Games]]
* [[Course:CPSC522/Identity Uncertainty|Identity Uncertainty]]
* [[Course:CPSC522/Generative Adversarial Networks|Generative Adversarial Networks]]

* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
*[[Course:CPSC522/User-Adaptive Information Visualization|User-Adaptive Information Visualization]]

==Existing Combinations (2020)==
* J3 [[Course:CPSC522/Monte Carlo Localization |Pedestrian localization for Indoor Environments]] (2020)
* J4 [[Course:CPSC522/Automation of hypothesis generation and testing in science|Automation of hypothesis generation and testing in science]] (2020)
* J5 [[Course:CPSC522/Deep Q Network |Prioritized Experience Replay]] (2020)
* F2 [[Course:CPSC522/Variation Auto-Encoders |Variational Auto-Encoders]] (2020)
* F3[[Course:CPSC522/Combining_Collaborative_Filtering_with_Personal_Agents_for_Better_Recommendations | Hybrid Recommendation Systems]] (2020)
* F4 [[Course:CPSC522/Online Pattern Analysis by Evolving Self-Organizing Maps|Online Pattern Analysis by Evolving Self-organizing Maps]] (2020)

==Existing Combinations (2018)==
===Neural Networks===
* [[Course:CPSC522/Financial Forecasting using LSTM Networks |Financial Forecasting using LSTM Networks]] (2018)
* [[Course:CPSC522/Character Level Language Models using LSTM|Character Level Language Models using LSTM]] (2018)
* [[Course:CPSC522/TextSummarizationUsingMachineLearning |Text Summarization using Machine Learning]] (2018)
* [[Course:CPSC522/Password_cracking_using_PCFGs_and_Neural_Networks|Password Cracking using Probabilistic Context Free Grammars and Neural Networks]] (2018)
* [[CNNs in Image Segmentation]](2018)
* [[Course:CPSC522/Image_Classification_With_Convolutional_Neural_Networks|Image Classification With Convolutional Neural Networks]] (2018)
* [[Image Colourization using Deep Learning]](2018)
* [[Course:CPSC522/StackedGAN|Stacked Generative Adversarial Networks]] (2018)

===Reinforcement Learning===
* [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] (2018)
* [[Course:CPSC522/Deep_Reinforcement_Learning|Deep Reinforcement Learning]] (2018)
* [[Course:CPSC522/Self_Improving_Machines|Self-Improving Machines]] (2018)
* [[Course:CPSC522/Adaptive_Network_Routing_using_ACO|Adaptive Network Routing using Ant Colony Optimization]] (2018)
* M0 [[Course:CPSC522/Grouped Prioritized Experience Replay (GPER)]] (2020)

===Decision-theoretic Planning===
* [[Course:CPSC522/Action_Selection_for_MDPs|Action Selection for MDPs]] (2018)
* [[Course:CPSC522/Rao_Blackwellized_Particle_Filtering|Rao-Blackwellized Particle Filtering]](2018)
===Relational Reasoning===
* [[Course:CPSC522/Transfer_Learning_with_Markov_Logic|Transfer Learning with Markov Logic]] (2018)
* [[Course:CPSC522/Cognitive_Robotics|Cognitive Robotics]] (2018)
===Applications===
* [[Course:CPSC522/Affect Prediction using Eye Gaze|Affect Prediction using Eye Gaze]] (2018)
* [[Course:CPSC522/Conflict-Driven Clause Learning for the Boolean Satisfiability Problem|Conflict-Driven Clause Learning for the Boolean Satisfiability Problem]] (2018)

==Existing Combinations (2019)==
* [[Course:CPSC522/Ontology Extraction|Ontology Extraction]]
* [[Course:CPSC522/Restricted Boltzmann Machines for Collaborative Filtering|Restricted Boltzmann Machines for Collaborative Filtering]]
* [[Course:CPSC522/Minimax Regret Preference Elicitation for Risky Prospects|Minimax Regret Preference Elicitation for Risky Prospects]]
* [[Course:CPSC522/Sequential Monte Carlo samplers|Sequential Monte Carlo samplers]]
* [[Course:CPSC522/FastSLAM|FastSLAM]]
* [[Course:CPSC522/SMC for PGMs|Sequential Monte Carlo for Probabilistic Graphical Models]]

==Future combinations (2016)==
* [[Course:CPSC522/Sentiment Analysis|Sentiment Analysis: Movie Reviews]]
* [[Course:CPSC522/Collaborative Filtering|Collaborative Filtering]]
* [[Course:CPSC522/List Recommendation|List Recommendation]]
* [[Course:CPSC522/Inactive Cookie Mapping via Trail Matching|Inactive Cookie Mapping via Trail Matching]]
* [[Course:CPSC522/Improve recommendation system by integration|Improve Recommendation System by Integration]]
* [[Course:CPSC522/Identity Uncertainty in a restaurant data-set|Identity Uncertainty in a restaurant data-set]]
* [[Course:CPSC522/Regularization_for_Neural_Networks|Regularization for Neural Networks]]
* [[Course:CPSC522/Spam Detection|Spam Detection]]
* [[Course:CPSC522/Titanic: Machine Learning from Disaster|Titanic: Machine Learning from Disaster]]
* [[Course:CPSC522/Automatic Classification of Morphological Heart Arrhythmia | Automatic Classification of Morphological Heart Arrhythmia]]
* [[Course:CPSC522/Linking Sentences in Asynchronous Conversations|Linking Sentences in Asynchronous Conversations]]
* [[Course:CPSC522/Generic Aspect-based Aggregation of Sentiments|Generic Aspect-based Aggregation of Sentiments]]
* [[Course:CPSC522/Graph Based keyword extraction|Graph Based Key-corporation Extraction]]
* [[Course:CPSC522/Improving the accuracy of Affect Prediction in an Intelligent Tutoring System|Improving the accuracy of Affect Prediction in an Intelligent Tutoring System]]
* [[Course:CPSC522/Improving Human Behavior Prediction in Simultaneous-Move Games|Improving Human Behavior Prediction in Simultaneous-Move Games]]
* [[Course:CPSC522/The Automation of Disease Diagnosis|The Automation of Disease Diagnosis]]
* [[Course:CPSC522/Analyzing online dating trends with Weka|Analyzing online dating trends with Weka]]

==Future combinations (2018)==
* [[Course:CPSC522/Artificial Intelligence and Economic Theory|Artificial Intelligence and Economic Theory]]
* [[Course:CPSC522/Weak Semantic Map|Weak Semantic Map: Simplified Chinese]]
* [[Course:CPSC522/Network Agent|Datacenter Traffic as Reinforcement Learning Problem]]
* [[Course:CPSC522/Baseilne_of_RSI|A Theoretical Baseline of Recursive Self-improvement]]
* [[Course:CPSC522/Text_Summarization_for_busy_people!| Text summarization for busy people!!]]
* [[Course:CPSC522/An_evaluation_on_selecting_and_applying_Recommendation_Methods | An evaluation on selecting and applying Recommendation Methods]]
* [[Course:CPSC522/Learning User Preferences of Motion Control | Learning User Preferences of Motion Control]]
* [[Course:CPSC522/Experiments_with_Reinforcement_Learning| Experiments with Reinforcement Learning]]
* [[Course:CPSC522/A_Comparison_of_LDA_and_NMF_for_Topic_Modeling_on_Literary_Themes| A Comparison of LDA and NMF for Topic Modeling on Literary Themes]]
* [[Course:CPSC522/Analysis of hierarchical prior for Language modeling | Analysis of hierarchical prior for Language modeling]]
* [[Better_caching_using_reinforcement_learning|Better Caching using reinforcement learning]]
* [[Course:CPSC522/Evaluation_of_ACO|Evaluating Ant Colony Optimization in a simulation]]
* [[Course:CPSC522/SLAM_And_Sensor_Quality|SLAM and Sensor Quality]]
* [[Text generation with LSTM and Markov Chain]]
* [[Course:CPSC522/Topology_and_Embedding_Multi-relational_Data|Topology and Embedding Multi-relational Data]]

== Future combinations (2019) ==
* [[Course:CPSC522/Reinforcement Learning with Linear Model of Reward Corruption|Reinforcement Learning with Linear Model of Reward Corruption]]
*
* [[Course:CPSC522/Adverserial Belief Propagation|Adversarial Belief Propagation]]
*
* [[Course:CPSC522/Using Subset Information with Matrix Factorization|Using Subset Information with Matrix Factorization]]
*
* [[Course:CPSC522/Learning Attention via Active Inference|Learning Attention via Active Inference]]
* [[Course:CPSC522/Regularization as an Alternative to Negative Sampling in KGs|Regularization as an Alternative to Negative Sampling in KGs]]
== Future combinations (2020) ==
* [[Course:CPSC522/Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations|Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations]]
* [[Course:CPSC522/Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps|Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps]]
==Suggested Unclaimed Pages==
Here are some possible topics for pages. This list is not meant to limit your imagination. Some of them might be better split into multiple pages. There are many other possible topics.

When claimed, these pages should be moved from this section to the table of contents above and to the [[Course:CPSC522/Index|Index]] of existing pages. To claim a page you have to actually create it and edit it (and have your name on the page, so everyone can see who has claimed it).

* [[Course:CPSC522/Probability general semantics|Probability - general semantics]] with infinitely many variables and/or variables with infinite domains
* [[Course:CPSC522/Representations of Conditional Distributions|Representations of Conditional Distributions]]
* [[Course:CPSC522/Recursive Conditioning|Recursive Conditioning]]
* [[Course:CPSC522/Parity Methods|Parity Methods for Probabilistic Inference]]
* [[Course:CPSC522/Matrix Factorization|Matrix Factorization]]
* [[Course:CPSC522/Utility|Utility]]
* [[Course:CPSC522/Multi-Attribute Utility|Multi-Attribute Utility]]
* [[Course:CPSC522/Preference Elicitation|Preference Elicitation]]
* [[Course:CPSC522/Mechanism Design|Mechanism Design]]
* [[Course:CPSC522/Logic Programming|Logic Programming]]
* [[Course:CPSC522/Negation as Failure|Negation as Failure]]
* [[Course:CPSC522/Equality-Identity|Equality/Identity]]
* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
* [[Course:CPSC522/Ontologies|Ontologies]]
* [[Course:CPSC522/Continual Learning|Continual Learning]]

Course:CPSC522/Grouped Prioritized Experience Replay (GPER)

2020-04-19T22:16:13Z

TommasoDAmico: Created page with "== Grouped Prioritized Experience Replay (GPER) == This page explores the concept of grouping prioritized experience replay memories to improve learning efficiency in temporal..."

Course:CPSC522

2020-04-19T22:15:33Z

TommasoDAmico:

{{Infobox_New_Course

|title=CPSC 522 Wiki

|picture=Image:wiki.png

|subject code=CPSC

|course number=522

|instructor=David Poole

|email=poole@cs.ubc.ca

|office= 109
|office hours= after class every day
|classroom= DMP 101

}}

[[Category:CPSC522]]
Welcome to [http://www.cs.ubc.ca/~poole/cs522/2019 CPSC 522] Wiki. This is where the participants are writing the textbook. See
http://www.cs.ubc.ca/~poole/cs522/2020/ for the main web page for the course.
==The 2020 Rules==
* These rules are editable, so you can change the rules.
* [[Course:CPSC522/StudentPresentations2020|2020 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 2 students per day.
* [[Course:CPSC522/January2020|January and February Assignment]]<nowiki/>s describes your assignments for January and February.
* [[Course:CPSC522/MarchApril2020|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

==Old (2018, 2019) Rules==
*[[Course:CPSC522/StudentPresentations2018|2018 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 3 students per day.
* [[Course:CPSC522/January2018|January Assignment]] describes your assignment for January.
* [[Course:CPSC522/February2018|February Assignment]] describes your assignment for February.
* [[Course:CPSC522/MarchApril2018|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

== Guidelines ==
* Keep each page as simple as possible (but not simpler); if a page starts to get complicated, consider splitting it.
* Write pages for your peers; they should all be written for incoming graduate students, and only assume background knowledge that is common among such students.
* All pages should obey the [[Course:CPSC522/Conventions|Syntax Conventions]]. If there is a design decision that you need to make that may have non-local implications, add it to the conventions.
* It should use formalism and mathematics when (and only when) the formalism make the description clearer. Use the code tags for math, e.g., <math>P(h\mid e) = \frac{P(h\land e)}{P(e)}.</math> It is worth your while to learn [https://www.latex-project.org/ Latex] if you don't already know it.
* If there is a simple case, and a more general case, give the simple case first. Making things complicated is easy; keeping them simple is difficult and we should strive for simplicity. Any complication needs to be carefully motivated.
* Use the "discussion" tab

Each Page should contain:
* A clear jargon-free description of what is going on. Keep jargon to a minimum.
* Motivating example(s) and, where appropriate, a simple pedagogical example (which may be different from the motivating examples) that is used to explain what is going on
* An argument of plausibility
* Evidence that it works
* Code and pseudo-code, where appropriate. This code should interact with other related code (e.g., [http://aipython.org AIFCA Python Distribution]) if possible. The code should be as simple as possible to implement the techniques. Consider adding exercises as to what can be improved or made more general or bullet-proof. Use a <code>code block</code> for (pseudo-)code (even multi-line code). You can also use the format in http://wiki.ubc.ca/Course:CPSC_320/Midterm_2_Reference_Sheet#Pseudocode (try both and see which better suits your needs).

==Foundations==
Please add your page here and in the [[Course:CPSC522/Index|Index]].

* [[Course:CPSC522/MyTest|My Test]]
===General===
* [[Course:CPSC522/AGI|Artificial General Intelligence]] (2018)
* [[Course:CPSC522/Swarm_Intelligence|Swarm Intelligence]] (2018)

===Control===
* [[Course:CPSC522/Control Theory|Control Theory]] (2016)
* [[Course:CPSC522/Hierarchical Control|Hierarchical Control]] (2016)

===Probability and Graphical Models===
* [[Course:CPSC522/Probability|Probability]] (2016)
* [[Course:CPSC522/Graphical Models|Graphical Models]] (2016)
* [[Course:CPSC522/Bayesian Networks|Bayesian Networks]] (2016)
* [[Course:CPSC522/Markov_Networks|Markov Networks]] (2016)
* [[Course:CPSC522/WeightedModelCounting|Weighted Model Counting]](2019)
====Temporal Models====
* [[Course:CPSC522/Markov Chains|Markov Chains]] (2018)
* [[Course:CPSC522/Hidden_Markov_Models|Hidden Markov Models]] (2016)
* [[Course:CPSC522/Kalman_filter|Kalman filter]] (2018)
* [[Course:CPSC522/Dynamic Bayesian Networks|Dynamic Bayesian Networks]] (2018)
====Inference====
* [[Course:CPSC522/Variable Elimination|Variable Elimination]] (2016)
* [[Course:CPSC522/MCMC|Markov Chain Monte Carlo]] (2016)
* [[Course:CPSC522/Particle Filtering|Particle Filtering]] (2016)
* [[Course:CPSC522/Treatment of Missing Data|Treatment of Missing Data]] (2019)
* [[Course:CPSC522/Bayesian Coresets|Bayesian Coresets]] (2019)
* J0 [[Course:CPSC522/Variational Inference|Variational Inference]] (2020)

====Causality====
* [[Course:CPSC522/Causality|Causality]] (2016)
====Representations of Conditional Probability====
* [[Course:CPSC522/Neural Network|Neural Network]] (2016)
* [[Course:CPSC522/Recurrent Neural Networks|Recurrent Neural Networks]] (2018)
* [[Course:CPSC522/Decision_Trees|Decision Trees]] (2018)
====Learning====
* [[Course:CPSC522/Learning Probabilistic Models with Complete Data|Learning Probabilistic Models with Complete Data]] (2018)
* [[Course:CPSC522/Support_Vector_Machines|Support Vector Machines]] (2018)
* [[Course:CPSC522/Ensemble Learning|Ensemble Learning]] (2018)
* J1 [[Course:CPSC522/Principal_Component_Analysis|Principal Component Analysis (PCA)]] (2020)
* J2 [[Course:CPSC 522/Self-Organizing Maps|Self-Organizing Maps]] (2020)
* F1 [[Course:CPSC 522/Progressive Neural Network|Progressive Neural Network]] (2020)
* F5 [[Course:CPSC522/Conditional GANs for Image to Image Translation|Conditional GANs for Image-To-Image Translation]] (2020)
* Term Project: [[Course:CPSC522/Alternative_Classifiers|Alternative Classifiers]] (2020)
===NLP===
* [[Course:CPSC522/Natural Language Processing | Natural Language Processing]] (2018)
* [[Course:CPSC522/PCFG|Probabilistic Context Free Grammars]] (2018)
===Utility and Preferences===

* [[Course:CPSC522/Bounded Rationality|Bounded Rationality]] (2018)
* [[Course:CPSC522/Elicitation of Factored Utilities|Elicitation of Factored Utilities]] (2019)

===Acting Under Uncertainty===
* [[Course:CPSC522/Decision Networks|Decision Networks]] (2016)
* [[Course:CPSC522/Markov Decision Process|Markov Decision Process]] (2016)
* F0 [[Course:CPSC522/Partially Observable Markov Decision Processes|Partially Observable Markov Decision Processes]] (2020)
* [[Course:CPSC522/Reinforcement Learning|Reinforcement Learning]] (2016)
* [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning with Function Approximation]] (2016)
* [[Course:CPSC522/Game Theory|Game Theory]] (2016)
* [[Course:CPSC522/Multi-Agent Systems|Multi-Agent Systems]] (2018)
* [[Course:CPSC522/Stochastic Optimization|Stochastic Optimization]] (2018)
* [[Course:CPSC522/Value of Information and Control|Value of Information]] (2019)

===Logic===
* [[Course:CPSC522/Abduction|Abduction]] (2018)
* [[Course:CPSC522/Knowledge Compilation|Knowledge Compilation]] (2016)
* [[Course:CPSC522/Predicate Calculus|Predicate Calculus]] (2016)
* [[Course:CPSC522/Markov Logic|Markov Logic]] (2018)
* [[Course:CPSC522/Higher Order Logic|Higher Order Logic]] (2018)
* [[Course:CPSC522/Ontology|Ontology]] (2019)

==Existing Combinations (2016)==
* [[Course:CPSC522/Recommendation System using Matrix Factorization|Recommendation System using Matrix Factorization]]
* [[Course:CPSC522/Latent Dirichlet Allocation|Latent Dirichlet Allocation]]
* [[Course:CPSC522/Deep Neural Network|Deep Neural Network and Game of Go]]
* [[Course:CPSC522/Problog|Problog]]
* [[Course:CPSC522/Maximum Entropy Markov Models|Maximum Entropy Markov Models]]
* [[Course:CPSC522/Future Directions for Semantic Systems|Ontology Search Engine]]
* [[Course:CPSC522/Convolutional Neural Networks|Convolutional Neural Networks]]
* [[Course:CPSC522/Learning Markov Logic Network Structure|Learning Markov Logic Network Structure]]
* [[Course:CPSC522/Decision Support System using Interactive Preference Elicitation|Decision Support System using Interactive Preference Elicitation]]
* [[Course:CPSC522/Predicting Affect of User's Interaction with an Intelligent Tutoring System|Predicting Affect of User's Interaction with an Intelligent Tutoring System]]
* [[Course:CPSC522/Record Linkage and identity uncertainty|Record Linkage and identity uncertainty]]
* [[Course:CPSC522/Robot Scientist|Robot Scientist]]
* [[Course:CPSC522/Density-Based Unsupervised Learning|Density-Based Unsupervised Learning]]
* [[Course:CPSC522/Predicting Human Behavior in Normal-Form Games|Predicting Human Behavior in Normal-Form Games]]
* [[Course:CPSC522/Identity Uncertainty|Identity Uncertainty]]
* [[Course:CPSC522/Generative Adversarial Networks|Generative Adversarial Networks]]

* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
*[[Course:CPSC522/User-Adaptive Information Visualization|User-Adaptive Information Visualization]]

==Existing Combinations (2020)==
* J3 [[Course:CPSC522/Monte Carlo Localization |Pedestrian localization for Indoor Environments]] (2020)
* J4 [[Course:CPSC522/Automation of hypothesis generation and testing in science|Automation of hypothesis generation and testing in science]] (2020)
* J5 [[Course:CPSC522/Deep Q Network |Prioritized Experience Replay]] (2020)
* F2 [[Course:CPSC522/Variation Auto-Encoders |Variational Auto-Encoders]] (2020)
* F3[[Course:CPSC522/Combining_Collaborative_Filtering_with_Personal_Agents_for_Better_Recommendations | Hybrid Recommendation Systems]] (2020)
* F4 [[Course:CPSC522/Online Pattern Analysis by Evolving Self-Organizing Maps|Online Pattern Analysis by Evolving Self-organizing Maps]] (2020)

==Existing Combinations (2018)==
===Neural Networks===
* [[Course:CPSC522/Financial Forecasting using LSTM Networks |Financial Forecasting using LSTM Networks]] (2018)
* [[Course:CPSC522/Character Level Language Models using LSTM|Character Level Language Models using LSTM]] (2018)
* [[Course:CPSC522/TextSummarizationUsingMachineLearning |Text Summarization using Machine Learning]] (2018)
* [[Course:CPSC522/Password_cracking_using_PCFGs_and_Neural_Networks|Password Cracking using Probabilistic Context Free Grammars and Neural Networks]] (2018)
* [[CNNs in Image Segmentation]](2018)
* [[Course:CPSC522/Image_Classification_With_Convolutional_Neural_Networks|Image Classification With Convolutional Neural Networks]] (2018)
* [[Image Colourization using Deep Learning]](2018)
* [[Course:CPSC522/StackedGAN|Stacked Generative Adversarial Networks]] (2018)

===Reinforcement Learning===
* [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] (2018)
* [[Course:CPSC522/Deep_Reinforcement_Learning|Deep Reinforcement Learning]] (2018)
* [[Course:CPSC522/Self_Improving_Machines|Self-Improving Machines]] (2018)
* [[Course:CPSC522/Adaptive_Network_Routing_using_ACO|Adaptive Network Routing using Ant Colony Optimization]] (2018)
* [[Course:CPSC522/Grouped Prioritized Experience Replay (GPER)]] (2020)

===Decision-theoretic Planning===
* [[Course:CPSC522/Action_Selection_for_MDPs|Action Selection for MDPs]] (2018)
* [[Course:CPSC522/Rao_Blackwellized_Particle_Filtering|Rao-Blackwellized Particle Filtering]](2018)
===Relational Reasoning===
* [[Course:CPSC522/Transfer_Learning_with_Markov_Logic|Transfer Learning with Markov Logic]] (2018)
* [[Course:CPSC522/Cognitive_Robotics|Cognitive Robotics]] (2018)
===Applications===
* [[Course:CPSC522/Affect Prediction using Eye Gaze|Affect Prediction using Eye Gaze]] (2018)
* [[Course:CPSC522/Conflict-Driven Clause Learning for the Boolean Satisfiability Problem|Conflict-Driven Clause Learning for the Boolean Satisfiability Problem]] (2018)

==Existing Combinations (2019)==
* [[Course:CPSC522/Ontology Extraction|Ontology Extraction]]
* [[Course:CPSC522/Restricted Boltzmann Machines for Collaborative Filtering|Restricted Boltzmann Machines for Collaborative Filtering]]
* [[Course:CPSC522/Minimax Regret Preference Elicitation for Risky Prospects|Minimax Regret Preference Elicitation for Risky Prospects]]
* [[Course:CPSC522/Sequential Monte Carlo samplers|Sequential Monte Carlo samplers]]
* [[Course:CPSC522/FastSLAM|FastSLAM]]
* [[Course:CPSC522/SMC for PGMs|Sequential Monte Carlo for Probabilistic Graphical Models]]

==Future combinations (2016)==
* [[Course:CPSC522/Sentiment Analysis|Sentiment Analysis: Movie Reviews]]
* [[Course:CPSC522/Collaborative Filtering|Collaborative Filtering]]
* [[Course:CPSC522/List Recommendation|List Recommendation]]
* [[Course:CPSC522/Inactive Cookie Mapping via Trail Matching|Inactive Cookie Mapping via Trail Matching]]
* [[Course:CPSC522/Improve recommendation system by integration|Improve Recommendation System by Integration]]
* [[Course:CPSC522/Identity Uncertainty in a restaurant data-set|Identity Uncertainty in a restaurant data-set]]
* [[Course:CPSC522/Regularization_for_Neural_Networks|Regularization for Neural Networks]]
* [[Course:CPSC522/Spam Detection|Spam Detection]]
* [[Course:CPSC522/Titanic: Machine Learning from Disaster|Titanic: Machine Learning from Disaster]]
* [[Course:CPSC522/Automatic Classification of Morphological Heart Arrhythmia | Automatic Classification of Morphological Heart Arrhythmia]]
* [[Course:CPSC522/Linking Sentences in Asynchronous Conversations|Linking Sentences in Asynchronous Conversations]]
* [[Course:CPSC522/Generic Aspect-based Aggregation of Sentiments|Generic Aspect-based Aggregation of Sentiments]]
* [[Course:CPSC522/Graph Based keyword extraction|Graph Based Key-corporation Extraction]]
* [[Course:CPSC522/Improving the accuracy of Affect Prediction in an Intelligent Tutoring System|Improving the accuracy of Affect Prediction in an Intelligent Tutoring System]]
* [[Course:CPSC522/Improving Human Behavior Prediction in Simultaneous-Move Games|Improving Human Behavior Prediction in Simultaneous-Move Games]]
* [[Course:CPSC522/The Automation of Disease Diagnosis|The Automation of Disease Diagnosis]]
* [[Course:CPSC522/Analyzing online dating trends with Weka|Analyzing online dating trends with Weka]]

==Future combinations (2018)==
* [[Course:CPSC522/Artificial Intelligence and Economic Theory|Artificial Intelligence and Economic Theory]]
* [[Course:CPSC522/Weak Semantic Map|Weak Semantic Map: Simplified Chinese]]
* [[Course:CPSC522/Network Agent|Datacenter Traffic as Reinforcement Learning Problem]]
* [[Course:CPSC522/Baseilne_of_RSI|A Theoretical Baseline of Recursive Self-improvement]]
* [[Course:CPSC522/Text_Summarization_for_busy_people!| Text summarization for busy people!!]]
* [[Course:CPSC522/An_evaluation_on_selecting_and_applying_Recommendation_Methods | An evaluation on selecting and applying Recommendation Methods]]
* [[Course:CPSC522/Learning User Preferences of Motion Control | Learning User Preferences of Motion Control]]
* [[Course:CPSC522/Experiments_with_Reinforcement_Learning| Experiments with Reinforcement Learning]]
* [[Course:CPSC522/A_Comparison_of_LDA_and_NMF_for_Topic_Modeling_on_Literary_Themes| A Comparison of LDA and NMF for Topic Modeling on Literary Themes]]
* [[Course:CPSC522/Analysis of hierarchical prior for Language modeling | Analysis of hierarchical prior for Language modeling]]
* [[Better_caching_using_reinforcement_learning|Better Caching using reinforcement learning]]
* [[Course:CPSC522/Evaluation_of_ACO|Evaluating Ant Colony Optimization in a simulation]]
* [[Course:CPSC522/SLAM_And_Sensor_Quality|SLAM and Sensor Quality]]
* [[Text generation with LSTM and Markov Chain]]
* [[Course:CPSC522/Topology_and_Embedding_Multi-relational_Data|Topology and Embedding Multi-relational Data]]

== Future combinations (2019) ==
* [[Course:CPSC522/Reinforcement Learning with Linear Model of Reward Corruption|Reinforcement Learning with Linear Model of Reward Corruption]]
*
* [[Course:CPSC522/Adverserial Belief Propagation|Adversarial Belief Propagation]]
*
* [[Course:CPSC522/Using Subset Information with Matrix Factorization|Using Subset Information with Matrix Factorization]]
*
* [[Course:CPSC522/Learning Attention via Active Inference|Learning Attention via Active Inference]]
* [[Course:CPSC522/Regularization as an Alternative to Negative Sampling in KGs|Regularization as an Alternative to Negative Sampling in KGs]]
== Future combinations (2020) ==
* [[Course:CPSC522/Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations|Improving Prediction Accuracy of User Cognitive Abilities for User-Adaptive Narrative Visualizations]]
* [[Course:CPSC522/Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps|Exploring Results of Conditional Generative Adversarial Networks with Self-Organizing Maps]]
==Suggested Unclaimed Pages==
Here are some possible topics for pages. This list is not meant to limit your imagination. Some of them might be better split into multiple pages. There are many other possible topics.

When claimed, these pages should be moved from this section to the table of contents above and to the [[Course:CPSC522/Index|Index]] of existing pages. To claim a page you have to actually create it and edit it (and have your name on the page, so everyone can see who has claimed it).

* [[Course:CPSC522/Probability general semantics|Probability - general semantics]] with infinitely many variables and/or variables with infinite domains
* [[Course:CPSC522/Representations of Conditional Distributions|Representations of Conditional Distributions]]
* [[Course:CPSC522/Recursive Conditioning|Recursive Conditioning]]
* [[Course:CPSC522/Parity Methods|Parity Methods for Probabilistic Inference]]
* [[Course:CPSC522/Matrix Factorization|Matrix Factorization]]
* [[Course:CPSC522/Utility|Utility]]
* [[Course:CPSC522/Multi-Attribute Utility|Multi-Attribute Utility]]
* [[Course:CPSC522/Preference Elicitation|Preference Elicitation]]
* [[Course:CPSC522/Mechanism Design|Mechanism Design]]
* [[Course:CPSC522/Logic Programming|Logic Programming]]
* [[Course:CPSC522/Negation as Failure|Negation as Failure]]
* [[Course:CPSC522/Equality-Identity|Equality/Identity]]
* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
* [[Course:CPSC522/Ontologies|Ontologies]]
* [[Course:CPSC522/Continual Learning|Continual Learning]]

Sandbox:Grouped Prioritized Experience Replay

2020-04-19T22:04:33Z

File:Taxi-v3 full.png

2020-04-19T21:45:18Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Taxi-v3 OpenAi Gym game Illustration with passenger on taxi}}
|date=2020-04-19
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

File:Taxi-v3.png

2020-04-19T21:45:18Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Taxi-v3 OpenAi Gym game Illustration}}
|date=2020-04-19
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

File:Taxi mod big.png

2020-04-19T21:45:18Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Modified Taxi-v3 OpenAi Gym game}}
|date=2020-04-19
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-14T18:43:13Z

TommasoDAmico:

== Partially Observable Markov Decision Processes (POMDPs) ==
A Partially Observable Markov Decision Processes (POMDs) is a mathematical model for acting under uncertainty. It expands from the Markov Decision Process (MDP) by relaxing the constraint of having a fully observable state space. In this paper we will evaluate the underlying mathematical model and explore the potential of POMDPs for belief MDP.

Principal Author: Tommaso D'Amico

Collaborators: -

== Abstract ==
POMDPs are a type of Decision Network that expands from Markov Decision Processes by not requiring all states to be observable by the agent. POMDPs still maintain the same system dynamics of an MDP although the acting agent cannot always observe its current state but rather it needs to maintain a probability distribution over the set of possible states it may be in based on its observations and the underlying MPD.

=== Builds on ===
POMDPs is a mathematical model expanding from the concepts of [https://wiki.ubc.ca/Course:CPSC522/Decision_Networks Decision networks], specifically generalizing from the [[Course:CPSC522/Markov Decision Processes|Markov Decision Process]] algorithm for acting under uncertainty.

=== Related Pages ===
POMDPs are widely implemented in applications that interact with the real world, some examples are particle filtering techniques such as MC-POMDPs, an extension of [https://wiki.ubc.ca/Course:CPSC522/MCMC Markov Chains Monte Carlo] for POMDPs and [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning]].

POMDPs are also closely related to [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and [https://en.wikipedia.org/wiki/Markov_chain Markov Chains].

== Content ==

=== Introduction ===
Partially Observable Markov Decision Processes (POMDPs) are a type of Markov Process closely related to Markov Decision Processes (MDP) as:
* there exist a finite number of discrete states
* the next state is only determined by the current state and the current action taken by the agent
* there exists a probabilistic transition between states and controllable actions in each state
The way a POMDP differs from an MDP is that the agent is unsure of which state it is in as it has only partial observability of the environment states. It instead needs to develop a probability distribution over the set of states it believes to be in and condition its observations and the underlying MDP structure. A comparison can be drawn for clarity to the relationship of Markov Chains with Hidden Markov Models, as the latter too is an extension of the prior with reduced observability. In fact a helpful illustration of the difference among these models can be seen in the chart below:
{| class="wikitable"
|+'''Helpful Chart for Markov Model Segmentation'''
| colspan="2" rowspan="2" |
| colspan="2" rowspan="1" |'''Does the agent have control over state transition?'''
|-
|no
|yes
|-
| colspan="1" rowspan="2" |'''Are the states fully observable?'''
|yes
|Markov Chain
|Markov Decision Process
|-
|no
|Hidden Markov Model
|Partilly Observable Markov Decision Process
|}

==== POMDP versus MPD ====
MPD is more tractable to solve and is relatively easy to specify although it assumes perfect knowledge of the states which is often unlikely for many use cases.

POMDP on the other hand treats all sources of uncertainty uniformly and allows for information gathering actions, although it is hugely intractable to solve optimally.
=== Formal Definition ===
[[File:POMDP.io.png|thumb|Partially Obsevable Markov Decision Process example (POMDP)|623x623px]]
Formally a POMDP working in discrete-time models the relationship between an agent and its environment<ref>Åström, K.J. “Optimal Control of Markov Processes with Incomplete State Information.” ''Journal of Mathematical Analysis and Applications'' 10, no. 1 (February 1965): 174–205. <nowiki>https://doi.org/10.1016/0022-247X(65)90154-X</nowiki>.</ref>. This is commonly done with a 7-tuple <math>(S,A,T,R,\Omega, O,\gamma)</math>where:
*<math>S</math>is a set of all states
* <math>A
</math>is a set of all actions
* <math>T
</math>is a set that specifies the conditional probability of the next state givent he previous state and action
* <math>R:S \times A\rightarrow \R
</math>is the reward function
* <math>\Omega</math>is the set of observations
* <math>O</math>is the set of conditional observation probabilities
* <math>\gamma \in [0,1]
</math>is the discount factor
At each time step the environment is in state <math>s \in S
</math>. The agent takes action <math>a \in A
</math>, which causes the environment to transition to <math>s'
</math>with probability given by <math>T(s' | s,a).
</math>at the same time the agent receives an observation <math>o \in \Omega
</math>which is dependent on the new environment state <math>s'

</math>and the action <math>a
</math>just done by the agent, this is described by the probability distribution of <math>O(o|s',a)
</math>. This state and action is then used to develop a reward <math>r
</math>equal to <math>R(s,a)
</math>. This process then repeats for the next time step until the agent completes its task or to infinity. The goal is for the agent to maximize its expected future discounted reward: <math>E[ \sum_{t=0}^\infty\gamma^tr_t ]
</math>, where <math>r_t
</math>is the reward earned at time <math>t

</math>. <math>\gamma
</math>is the discount factor that determines how much immediate rewards are favoured over distant rewards. When <math>\gamma = 0

</math>the agent only cares about which action will yield the largest expected immediate reward, while if <math>\gamma = 1

</math>the agent cares about maximizing the expected sum of future rewards.

==== Belief Update ====
After executing one time step an agent needs to update its belief of the state of the environment it is in<ref name=":0">Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. “Planning and Acting in Partially Observable Stochastic Domains.” ''Artificial Intelligence'' 101, no. 1–2 (May 1998): 99–134. <nowiki>https://doi.org/10.1016/S0004-3702(98)00023-X</nowiki>.</ref>. Since we assume a ''Markovian'' state space, all we need to describe to execute this step is our prior state belief <math>b</math>, the last action <math>a</math>taken by the agent and the last observation made <math>o</math>. The belief update is an actionless step and is therefore the same as seen on a [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Model] belief update.

The belief state defined as <math>b</math> is a function over all states <math>S</math> from [0,1] that sums up to 1.

The update step can be denoted as <math>b' = \tau(b,a,o)</math>.

After reaching state <math>s'</math>, the agent observes <math>o \in \Omega
</math>with probability <math>O(o|s',a)
</math>as described in the prior section.

If we then let <math>b</math> be a probability distribution over the state space <math>S</math>then <math>b(s)</math>denotes the probability that the environment is in state <math>s</math>. Given <math>b(s)</math>, then after taking an action <math>a</math>and an observation <math>o</math>,

<math display="block">b'(s') = \eta O(o|s',a) \sum_{s \in S} T(s' |s,a)b(s)</math>

where <math>\eta = 1 / Pr(o|b,a)</math> is used as a normalising constant with

<math display="block">Pr(o|b,a) = \sum_{s' \in S} O(o|s',a) \sum_{s \in S} T(s' | s,a)b(s)</math>

==== Interpretation of Definition ====
[[File:DroneSurveilance.gif|thumb|Drone Navigating around space avoiding ground agent using POMDP|439x439px]]
From the above definition the agent does not directly observe its environment. It instead has to make decisions about the true environment state under uncertainty. However, by interacting with the environment and receiving observations the agent is able to update its belief of the true state by updating the probability distribution of the current state. Through this property of the algorithm the extrapolated optimal behaviour may often include actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in future time steps.

If we compare the formal definition of the POMDP described above with that of MDP we would have a very similar structure with the exception that the MDP algorithm would not include the conditional observation probabilities set <math>O</math>as it is always certain of the observed true state.

An example of a POMDP in action can be seen on the left, this animation illustrates a drone (in yellow) navigating a tiled environment. Its objective is to reach the oposing green square without coming into contact with the ground agent (in red). The blue squares represent the drone's observable environment. Since the drone is not capale of observing the state of the ground agent at all times, MDP is not tractable for this task, POMDP enables it to estimate a probability distribution of the likely states the ground agent might be in and act accordingly.

=== Belief MDP ===
A Markovian belief state allows a POMDP to be formulated as an Markov Decision Process where every belief is a state. The resulting belief MDP will be defined on a continuous state space even though the the originating POMDP has a finite number of states. This is because there are infinite number of probability distributions over the state set.

The belief MDP is formally described as a tuple <math>(B,A,\tau ,r ,\gamma )</math>where

<math>B</math>is the set of belief states over the POMDP states

<math>A</math>is the same finite set of actions as in the POMDP algorithm

<math>\tau</math>is the belief state transition function

<math>r: B \times A \rightarrow \R</math>is the reward function on belief states

<math>\gamma</math>is the discount factor equal to the one in the original POMDP

from these values <math>\tau
</math>and <math>r</math>are derived from the original POMDP via

<math display="block">\tau (b,a,b') = \sum_{o \in \Omega} Pr(b'|b,a,o)Pr(o|a,b)</math>

where <math>Pr(o|a,b)</math> is the value derived in the previous section and

<math display="block">Pr(b'|b,a,o) = \begin{cases} 1, & \text{if the belief update with arguments } b,a,o \text{ returns } b' \\ 0, & \text{otherwise} \end{cases}

</math>

and the reward function is the expected reward from the POMDP reward function over the belief distribution as follows

<math display="block">r(b,a) = \sum_{s \in S} b(s)R(s,a)
</math>

By going through these steps the belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP.

This means we were able to take a partially observable discrete space system and convert it to a continuous space fully observable belief system.

[[File:POMDP policy.png|thumb|POMDP decomposed into a state estimator and a policy.]]

=== Policy and Value Function ===
On a Belief MDP the agent is now able to choose between all possible actions to take as it may believe to be in any state with a given probability. We therefore must define a new variable <math>\pi </math>that describes an action <math>a = \pi(b)</math>given a certain belief <math>b</math><ref name=":0" />.

The expected reward for the policy <math>\pi
</math>starting from belief <math>b_0</math>is <math display="block">
V^\pi(b_0) = \sum_{t=0}^\infty \gamma^t r(b_t, a_t) = \sum_{t=0}^\infty \gamma^t E\Bigl[ R(s_t,a_t) \mid b_0, \pi \Bigr]
</math>where again <math>\gamma < 1</math>is the discount factor.

By optimizing for long-term reward we can obtain the optimal policy <math display="block">\pi ^{*}={\underset {\pi }{{\mbox{argmax}}}}\ V^{\pi }(b_{0})</math>where <math>b_0</math>is the initial state.

The optimal value function therefore can be described as

<math display="block">{\displaystyle V^{*}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }\Pr(o\mid b,a)V^{*}(\tau (b,a,o)){\Bigr ]}}</math>

The value function is piecewise linear and convex for a finite-horizon POMDP<ref>Smallwood, R. D., & Sondik, E. J. (1973). ''The Optimal Control of Partially Observable Markov Processes over a Finite Horizon. Operations Research, 21(5), 1071–1088.'' doi:10.1287/opre.21.5.1071 </ref>. For an infinite-horizon POMDP a finite vector set can approximate <math>V^*</math>with the use of dynamic programming techniques.

=== Applications of POMDP ===

==== Pursuit-Evasion ====
Imagine a fleet of robots in a constrained environment, assign one robot to pursuit the others. The pursuer's state is known, but the evader's state is only partially observed. POMDP can be applied by the evaders in a multi-agent search fashion to observe the environment and build a belief of the pursuer's location.<ref>{{Cite journal|last=Hollinger, Singh|first=|date=|title=Efficient Multi-robot Search for a Moving Target|url=https://journals.sagepub.com/doi/10.1177/0278364908099853|journal=The International Journal of Robotics Research|volume=|pages=|via=}}</ref>

==== Sensor Placement ====
A store may have a limited amount of cameras to allocate in its interior to monitor its environment, since the "world " will be partially observable, using POMDP can help reconstruct intruder position or in the contrary facilitate "stealthy" movement.

=== Conclusion ===
Probability theory is a powerful tool for modelling action under uncertainty, thanks to the Markov assumption many algorithms have become easy to implement for this purpose. POMDPs are one of the broader algorithms in this category as they take structure from highly constrained algorithms such as MDPs and relax assumptions of observability to allow for more real-world problem solving applications.

== Annotated Bibliography ==
[1] Åström, K.J. “Optimal Control of Markov Processes with Incomplete State Information.” ''Journal of Mathematical Analysis and Applications'' 10, no. 1 (February 1965): 174–205. <nowiki>https://doi.org/10.1016/0022-247X(65)90154-X</nowiki>.

[2] Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. “Planning and Acting in Partially Observable Stochastic Domains.” ''Artificial Intelligence'' 101, no. 1–2 (May 1998): 99–134. <nowiki>https://doi.org/10.1016/S0004-3702(98)00023-X</nowiki>.

[3] Smallwood, R. D., & Sondik, E. J. (1973). ''The Optimal Control of Partially Observable Markov Processes over a Finite Horizon. Operations Research, 21(5), 1071–1088.'' doi:10.1287/opre.21.5.1071

== 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.

Course:CPSC522

2020-03-13T20:50:38Z

TommasoDAmico:

{{Infobox_New_Course

|title=CPSC 522 Wiki

|picture=Image:wiki.png

|subject code=CPSC

|course number=522

|instructor=David Poole

|email=poole@cs.ubc.ca

|office= 109
|office hours= after class every day
|classroom= DMP 101

}}

[[Category:CPSC522]]
Welcome to [http://www.cs.ubc.ca/~poole/cs522/2019 CPSC 522] Wiki. This is where the participants are writing the textbook. See
http://www.cs.ubc.ca/~poole/cs522/2020/ for the main web page for the course.
==The 2020 Rules==
* These rules are editable, so you can change the rules.
* [[Course:CPSC522/StudentPresentations2020|2020 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 2 students per day.
* [[Course:CPSC522/January2020|January and February Assignment]]<nowiki/>s describes your assignments for January and February.
* [[Course:CPSC522/MarchApril2019|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

==Old (2018, 2019) Rules==
*[[Course:CPSC522/StudentPresentations2018|2018 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 3 students per day.
* [[Course:CPSC522/January2018|January Assignment]] describes your assignment for January.
* [[Course:CPSC522/February2018|February Assignment]] describes your assignment for February.
* [[Course:CPSC522/MarchApril2018|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

== Guidelines ==
* Keep each page as simple as possible (but not simpler); if a page starts to get complicated, consider splitting it.
* Write pages for your peers; they should all be written for incoming graduate students, and only assume background knowledge that is common among such students.
* All pages should obey the [[Course:CPSC522/Conventions|Syntax Conventions]]. If there is a design decision that you need to make that may have non-local implications, add it to the conventions.
* It should use formalism and mathematics when (and only when) the formalism make the description clearer. Use the code tags for math, e.g., <math>P(h\mid e) = \frac{P(h\land e)}{P(e)}.</math> It is worth your while to learn [https://www.latex-project.org/ Latex] if you don't already know it.
* If there is a simple case, and a more general case, give the simple case first. Making things complicated is easy; keeping them simple is difficult and we should strive for simplicity. Any complication needs to be carefully motivated.
* Use the "discussion" tab

Each Page should contain:
* A clear jargon-free description of what is going on. Keep jargon to a minimum.
* Motivating example(s) and, where appropriate, a simple pedagogical example (which may be different from the motivating examples) that is used to explain what is going on
* An argument of plausibility
* Evidence that it works
* Code and pseudo-code, where appropriate. This code should interact with other related code (e.g., [http://aipython.org AIFCA Python Distribution]) if possible. The code should be as simple as possible to implement the techniques. Consider adding exercises as to what can be improved or made more general or bullet-proof. Use a <code>code block</code> for (pseudo-)code (even multi-line code). You can also use the format in http://wiki.ubc.ca/Course:CPSC_320/Midterm_2_Reference_Sheet#Pseudocode (try both and see which better suits your needs).

==Foundations==
Please add your page here and in the [[Course:CPSC522/Index|Index]].

* [[Course:CPSC522/MyTest|My Test]]
===General===
* [[Course:CPSC522/AGI|Artificial General Intelligence]] (2018)
* [[Course:CPSC522/Swarm_Intelligence|Swarm Intelligence]] (2018)

===Control===
* [[Course:CPSC522/Control Theory|Control Theory]] (2016)
* [[Course:CPSC522/Hierarchical Control|Hierarchical Control]] (2016)

===Probability and Graphical Models===
* [[Course:CPSC522/Probability|Probability]] (2016)
* [[Course:CPSC522/Graphical Models|Graphical Models]] (2016)
* [[Course:CPSC522/Bayesian Networks|Bayesian Networks]] (2016)
* [[Course:CPSC522/Markov_Networks|Markov Networks]] (2016)
* [[Course:CPSC522/WeightedModelCounting|Weighted Model Counting]](2019)
====Temporal Models====
* [[Course:CPSC522/Markov Chains|Markov Chains]] (2018)
* [[Course:CPSC522/Hidden_Markov_Models|Hidden Markov Models]] (2016)
* [[Course:CPSC522/Kalman_filter|Kalman filter]] (2018)
* [[Course:CPSC522/Dynamic Bayesian Networks|Dynamic Bayesian Networks]] (2018)
====Inference====
* [[Course:CPSC522/Variable Elimination|Variable Elimination]] (2016)
* [[Course:CPSC522/MCMC|Markov Chain Monte Carlo]] (2016)
* [[Course:CPSC522/Particle Filtering|Particle Filtering]] (2016)
* [[Course:CPSC522/Treatment of Missing Data|Treatment of Missing Data]] (2019)
* [[Course:CPSC522/Bayesian Coresets|Bayesian Coresets]] (2019)
* J0 [[Course:CPSC522/Variational Inference|Variational Inference]] (2020)

====Causality====
* [[Course:CPSC522/Causality|Causality]] (2016)
====Representations of Conditional Probability====
* [[Course:CPSC522/Neural Network|Neural Network]] (2016)
* [[Course:CPSC522/Recurrent Neural Networks|Recurrent Neural Networks]] (2018)
* [[Course:CPSC522/Decision_Trees|Decision Trees]] (2018)
====Learning====
* [[Course:CPSC522/Learning Probabilistic Models with Complete Data|Learning Probabilistic Models with Complete Data]] (2018)
* [[Course:CPSC522/Support_Vector_Machines|Support Vector Machines]] (2018)
* [[Course:CPSC522/Ensemble Learning|Ensemble Learning]] (2018)
* J1 [[Course:CPSC522/Principal_Component_Analysis|Principal Component Analysis (PCA)]] (2020)
* J2 [[Course:CPSC 522/Self-Organizing Maps|Self-Organizing Maps]] (2020)
* F1 [[Course:CPSC 522/Progressive Neural Network|Progressive Neural Network]] (2020)
* F5 [[Course:CPSC522/Conditional GANs for Image to Image Translation|Conditional GANs for Image-To-Image Translation]] (2020)
===NLP===
* [[Course:CPSC522/Natural Language Processing | Natural Language Processing]] (2018)
* [[Course:CPSC522/PCFG|Probabilistic Context Free Grammars]] (2018)

===Utility and Preferences===

* [[Course:CPSC522/Bounded Rationality|Bounded Rationality]] (2018)
* [[Course:CPSC522/Elicitation of Factored Utilities|Elicitation of Factored Utilities]] (2019)

===Acting Under Uncertainty===
* [[Course:CPSC522/Decision Networks|Decision Networks]] (2016)
* [[Course:CPSC522/Markov Decision Process|Markov Decision Process]] (2016)
* F0 [[Course:CPSC522/Partially Observable Markov Decision Processes|Partially Observable Markov Decision Processes]] (2020)
* [[Course:CPSC522/Reinforcement Learning|Reinforcement Learning]] (2016)
* [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning with Function Approximation]] (2016)
* [[Course:CPSC522/Game Theory|Game Theory]] (2016)
* [[Course:CPSC522/Multi-Agent Systems|Multi-Agent Systems]] (2018)
* [[Course:CPSC522/Stochastic Optimization|Stochastic Optimization]] (2018)
* [[Course:CPSC522/Value of Information and Control|Value of Information]] (2019)

===Logic===
* [[Course:CPSC522/Abduction|Abduction]] (2018)
* [[Course:CPSC522/Knowledge Compilation|Knowledge Compilation]] (2016)
* [[Course:CPSC522/Predicate Calculus|Predicate Calculus]] (2016)
* [[Course:CPSC522/Markov Logic|Markov Logic]] (2018)
* [[Course:CPSC522/Higher Order Logic|Higher Order Logic]] (2018)
* [[Course:CPSC522/Ontology|Ontology]] (2019)

==Existing Combinations (2016)==
* [[Course:CPSC522/Recommendation System using Matrix Factorization|Recommendation System using Matrix Factorization]]
* [[Course:CPSC522/Latent Dirichlet Allocation|Latent Dirichlet Allocation]]
* [[Course:CPSC522/Deep Neural Network|Deep Neural Network and Game of Go]]
* [[Course:CPSC522/Problog|Problog]]
* [[Course:CPSC522/Maximum Entropy Markov Models|Maximum Entropy Markov Models]]
* [[Course:CPSC522/Future Directions for Semantic Systems|Ontology Search Engine]]
* [[Course:CPSC522/Convolutional Neural Networks|Convolutional Neural Networks]]
* [[Course:CPSC522/Learning Markov Logic Network Structure|Learning Markov Logic Network Structure]]
* [[Course:CPSC522/Decision Support System using Interactive Preference Elicitation|Decision Support System using Interactive Preference Elicitation]]
* [[Course:CPSC522/Predicting Affect of User's Interaction with an Intelligent Tutoring System|Predicting Affect of User's Interaction with an Intelligent Tutoring System]]
* [[Course:CPSC522/Record Linkage and identity uncertainty|Record Linkage and identity uncertainty]]
* [[Course:CPSC522/Robot Scientist|Robot Scientist]]
* [[Course:CPSC522/Density-Based Unsupervised Learning|Density-Based Unsupervised Learning]]
* [[Course:CPSC522/Predicting Human Behavior in Normal-Form Games|Predicting Human Behavior in Normal-Form Games]]
* [[Course:CPSC522/Identity Uncertainty|Identity Uncertainty]]
* [[Course:CPSC522/Generative Adversarial Networks|Generative Adversarial Networks]]

* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
*[[Course:CPSC522/User-Adaptive Information Visualization|User-Adaptive Information Visualization]]

==Existing Combinations (2020)==
* J3 [[Course:CPSC522/Monte Carlo Localization |Pedestrian localization for Indoor Environments]] (2020)
* J4 [[Course:CPSC522/Automation of hypothesis generation and testing in science|Automation of hypothesis generation and testing in science]] (2020)
* J5 [[Course:CPSC522/Deep Q Network |Prioritized Experience Replay]] (2020)
* F2 [[Course:CPSC522/Variation Auto-Encoders |Variational Auto-Encoders]] (2020)
* F3[[Course:CPSC522/Combining_Collaborative_Filtering_with_Personal_Agents_for_Better_Recommendations | Hybrid Recommendation Systems]] (2020)
* F4 [[Course:CPSC522/Online Pattern Analysis by Evolving Self-Organizing Maps|Online Pattern Analysis by Evolving Self-organizing Maps]] (2020)

==Existing Combinations (2018)==
===Neural Networks===
* [[Course:CPSC522/Financial Forecasting using LSTM Networks |Financial Forecasting using LSTM Networks]] (2018)
* [[Course:CPSC522/Character Level Language Models using LSTM|Character Level Language Models using LSTM]] (2018)
* [[Course:CPSC522/TextSummarizationUsingMachineLearning |Text Summarization using Machine Learning]] (2018)
* [[Course:CPSC522/Password_cracking_using_PCFGs_and_Neural_Networks|Password Cracking using Probabilistic Context Free Grammars and Neural Networks]] (2018)
* [[CNNs in Image Segmentation]](2018)
* [[Course:CPSC522/Image_Classification_With_Convolutional_Neural_Networks|Image Classification With Convolutional Neural Networks]] (2018)
* [[Image Colourization using Deep Learning]](2018)
* [[Course:CPSC522/StackedGAN|Stacked Generative Adversarial Networks]] (2018)

===Reinforcement Learning===
* [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] (2018)
* [[Course:CPSC522/Deep_Reinforcement_Learning|Deep Reinforcement Learning]] (2018)
* [[Course:CPSC522/Self_Improving_Machines|Self-Improving Machines]] (2018)
* [[Course:CPSC522/Adaptive_Network_Routing_using_ACO|Adaptive Network Routing using Ant Colony Optimization]] (2018)
===Decision-theoretic Planning===
* [[Course:CPSC522/Action_Selection_for_MDPs|Action Selection for MDPs]] (2018)
* [[Course:CPSC522/Rao_Blackwellized_Particle_Filtering|Rao-Blackwellized Particle Filtering]](2018)
===Relational Reasoning===
* [[Course:CPSC522/Transfer_Learning_with_Markov_Logic|Transfer Learning with Markov Logic]] (2018)
* [[Course:CPSC522/Cognitive_Robotics|Cognitive Robotics]] (2018)
===Applications===
* [[Course:CPSC522/Affect Prediction using Eye Gaze|Affect Prediction using Eye Gaze]] (2018)
* [[Course:CPSC522/Conflict-Driven Clause Learning for the Boolean Satisfiability Problem|Conflict-Driven Clause Learning for the Boolean Satisfiability Problem]] (2018)

==Existing Combinations (2019)==
* [[Course:CPSC522/Ontology Extraction|Ontology Extraction]]
* [[Course:CPSC522/Restricted Boltzmann Machines for Collaborative Filtering|Restricted Boltzmann Machines for Collaborative Filtering]]
* [[Course:CPSC522/Minimax Regret Preference Elicitation for Risky Prospects|Minimax Regret Preference Elicitation for Risky Prospects]]
* [[Course:CPSC522/Sequential Monte Carlo samplers|Sequential Monte Carlo samplers]]
* [[Course:CPSC522/FastSLAM|FastSLAM]]
* [[Course:CPSC522/SMC for PGMs|Sequential Monte Carlo for Probabilistic Graphical Models]]

==Future combinations (2016)==
* [[Course:CPSC522/Sentiment Analysis|Sentiment Analysis: Movie Reviews]]
* [[Course:CPSC522/Collaborative Filtering|Collaborative Filtering]]
* [[Course:CPSC522/List Recommendation|List Recommendation]]
* [[Course:CPSC522/Inactive Cookie Mapping via Trail Matching|Inactive Cookie Mapping via Trail Matching]]
* [[Course:CPSC522/Improve recommendation system by integration|Improve Recommendation System by Integration]]
* [[Course:CPSC522/Identity Uncertainty in a restaurant data-set|Identity Uncertainty in a restaurant data-set]]
* [[Course:CPSC522/Regularization_for_Neural_Networks|Regularization for Neural Networks]]
* [[Course:CPSC522/Spam Detection|Spam Detection]]
* [[Course:CPSC522/Titanic: Machine Learning from Disaster|Titanic: Machine Learning from Disaster]]
* [[Course:CPSC522/Automatic Classification of Morphological Heart Arrhythmia | Automatic Classification of Morphological Heart Arrhythmia]]
* [[Course:CPSC522/Linking Sentences in Asynchronous Conversations|Linking Sentences in Asynchronous Conversations]]
* [[Course:CPSC522/Generic Aspect-based Aggregation of Sentiments|Generic Aspect-based Aggregation of Sentiments]]
* [[Course:CPSC522/Graph Based keyword extraction|Graph Based Key-corporation Extraction]]
* [[Course:CPSC522/Improving the accuracy of Affect Prediction in an Intelligent Tutoring System|Improving the accuracy of Affect Prediction in an Intelligent Tutoring System]]
* [[Course:CPSC522/Improving Human Behavior Prediction in Simultaneous-Move Games|Improving Human Behavior Prediction in Simultaneous-Move Games]]
* [[Course:CPSC522/The Automation of Disease Diagnosis|The Automation of Disease Diagnosis]]
* [[Course:CPSC522/Analyzing online dating trends with Weka|Analyzing online dating trends with Weka]]

==Future combinations (2018)==
* [[Course:CPSC522/Artificial Intelligence and Economic Theory|Artificial Intelligence and Economic Theory]]
* [[Course:CPSC522/Weak Semantic Map|Weak Semantic Map: Simplified Chinese]]
* [[Course:CPSC522/Network Agent|Datacenter Traffic as Reinforcement Learning Problem]]
* [[Course:CPSC522/Baseilne_of_RSI|A Theoretical Baseline of Recursive Self-improvement]]
* [[Course:CPSC522/Text_Summarization_for_busy_people!| Text summarization for busy people!!]]
* [[Course:CPSC522/An_evaluation_on_selecting_and_applying_Recommendation_Methods | An evaluation on selecting and applying Recommendation Methods]]
* [[Course:CPSC522/Learning User Preferences of Motion Control | Learning User Preferences of Motion Control]]
* [[Course:CPSC522/Experiments_with_Reinforcement_Learning| Experiments with Reinforcement Learning]]
* [[Course:CPSC522/A_Comparison_of_LDA_and_NMF_for_Topic_Modeling_on_Literary_Themes| A Comparison of LDA and NMF for Topic Modeling on Literary Themes]]
* [[Course:CPSC522/Analysis of hierarchical prior for Language modeling | Analysis of hierarchical prior for Language modeling]]
* [[Better_caching_using_reinforcement_learning|Better Caching using reinforcement learning]]
* [[Course:CPSC522/Evaluation_of_ACO|Evaluating Ant Colony Optimization in a simulation]]
* [[Course:CPSC522/SLAM_And_Sensor_Quality|SLAM and Sensor Quality]]
* [[Text generation with LSTM and Markov Chain]]
* [[Course:CPSC522/Topology_and_Embedding_Multi-relational_Data|Topology and Embedding Multi-relational Data]]

== Future combinations (2019) ==
* [[Course:CPSC522/Reinforcement Learning with Linear Model of Reward Corruption|Reinforcement Learning with Linear Model of Reward Corruption]]
*
* [[Course:CPSC522/Adverserial Belief Propagation|Adversarial Belief Propagation]]
*
* [[Course:CPSC522/Using Subset Information with Matrix Factorization|Using Subset Information with Matrix Factorization]]
*
* [[Course:CPSC522/Learning Attention via Active Inference|Learning Attention via Active Inference]]
* [[Course:CPSC522/Regularization as an Alternative to Negative Sampling in KGs|Regularization as an Alternative to Negative Sampling in KGs]]
==Suggested Unclaimed Pages==
Here are some possible topics for pages. This list is not meant to limit your imagination. Some of them might be better split into multiple pages. There are many other possible topics.

When claimed, these pages should be moved from this section to the table of contents above and to the [[Course:CPSC522/Index|Index]] of existing pages. To claim a page you have to actually create it and edit it (and have your name on the page, so everyone can see who has claimed it).

* [[Course:CPSC522/Probability general semantics|Probability - general semantics]] with infinitely many variables and/or variables with infinite domains
* [[Course:CPSC522/Representations of Conditional Distributions|Representations of Conditional Distributions]]
* [[Course:CPSC522/Recursive Conditioning|Recursive Conditioning]]
* [[Course:CPSC522/Parity Methods|Parity Methods for Probabilistic Inference]]
* [[Course:CPSC522/Matrix Factorization|Matrix Factorization]]
* [[Course:CPSC522/Utility|Utility]]
* [[Course:CPSC522/Multi-Attribute Utility|Multi-Attribute Utility]]
* [[Course:CPSC522/Preference Elicitation|Preference Elicitation]]
* [[Course:CPSC522/Mechanism Design|Mechanism Design]]
* [[Course:CPSC522/Logic Programming|Logic Programming]]
* [[Course:CPSC522/Negation as Failure|Negation as Failure]]
* [[Course:CPSC522/Equality-Identity|Equality/Identity]]
* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
* [[Course:CPSC522/Ontologies|Ontologies]]
* [[Course:CPSC522/Continual Learning|Continual Learning]]

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-13T20:48:54Z

TommasoDAmico:

== Partially Observable Markov Decision Processes (POMDPs) ==
A Partially Observable Markov Decision Processes (POMDs) is a mathematical model for acting under uncertainty. It expands from the Markov Decision Process (MDP) by relaxing the constraint of having a fully observable state space. In this paper we will evaluate the underlying mathematical model and explore the potential of POMDPs for belief MDP.

Principal Author: Tommaso D'Amico

Collaborators: -

== Abstract ==
POMDPs are a type of Decision Network that expands from Markov Decision Processes by not requiring all states to be observable by the agent. POMDPs still maintain the same system dynamics of an MDP although the acting agent cannot always observe its current state but rather it needs to maintain a probability distribution over the set of possible states it may be in based on its observations and the underlying MPD.

=== Builds on ===
POMDPs is a mathematical model expanding from the concepts of [https://wiki.ubc.ca/Course:CPSC522/Decision_Networks Decision networks], specifically generalizing from the [[Course:CPSC522/Markov Decision Processes|Markov Decision Process]] algorithm for acting under uncertainty.

=== Related Pages ===
POMDPs are widely implemented in applications that interact with the real world, some examples are particle filtering techniques such as MC-POMDPs, an extension of [https://wiki.ubc.ca/Course:CPSC522/MCMC Markov Chains Monte Carlo] for POMDPs and [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning]].

POMDPs are also closely related to [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and [https://en.wikipedia.org/wiki/Markov_chain Markov Chains].

== Content ==

=== Introduction ===
Partially Observable Markov Decision Processes (POMDPs) are a type of Markov Process closely related to Markov Decision Processes (MDP) as:
* there exist a finite number of discrete states
* the next state is only determined by the current state and the current action taken by the agent
* there exists a probabilistic transition between states and controllable actions in each state
The way a POMDP differs from an MDP is that the agent is unsure of which state it is in as it has only partial observability of the environment states. It instead needs to develop a probability distribution over the set of states it believes to be in and condition its observations and the underlying MDP structure. A comparison can be drawn for clarity to the relationship of Markov Chains with Hidden Markov Models, as the latter too is an extension of the prior with reduced observability. In fact a helpful illustration of the difference among these models can be seen in the chart below:
{| class="wikitable"
|+'''Helpful Chart for Markov Model Segmentation'''
| colspan="2" rowspan="2" |
| colspan="2" rowspan="1" |'''Does the agent have control over state transition?'''
|-
|no
|yes
|-
| colspan="1" rowspan="2" |'''Are the states fully observable?'''
|yes
|Markov Chain
|Markov Decision Process
|-
|no
|Hidden Markov Model
|Partilly Observable Markov Decision Process
|}

==== POMDP versus MPD ====
MPD is more tractable to solve and is relatively easy to specify although it assumes perfect knowledge of the states which is often unlikely for many use cases.

POMDP on the other hand treats all sources of uncertainty uniformly and allows for information gathering actions, although it is hugely intractable to solve optimally.
=== Formal Definition ===
[[File:POMDP.io.png|thumb|Partially Obsevable Markov Decision Process example (POMDP)|623x623px]]
Formally a POMDP working in discrete-time models the relationship between an agent and its environment<ref>Åström, K.J. “Optimal Control of Markov Processes with Incomplete State Information.” ''Journal of Mathematical Analysis and Applications'' 10, no. 1 (February 1965): 174–205. <nowiki>https://doi.org/10.1016/0022-247X(65)90154-X</nowiki>.</ref>. This is commonly done with a 7-tuple <math>(S,A,T,R,\Omega, O,\gamma)</math>where:
*<math>S</math>is a set of all states
* <math>A
</math>is a set of all actions
* <math>T
</math>is a set that specifies the conditional probability of the next state givent he previous state and action
* <math>R:S \times A\rightarrow \R
</math>is the reward function
* <math>\Omega</math>is the set of observations
* <math>O</math>is the set of conditional observation probabilities
* <math>\gamma \in [0,1]
</math>is the discount factor
At each time step the environment is in state <math>s \in S
</math>. The agent takes action <math>a \in A
</math>, which causes the environment to transition to <math>s'
</math>with probability given by <math>T(s' | s,a).
</math>at the same time the agent receives an observation <math>o \in \Omega
</math>which is dependent on the new environment state <math>s'

</math>and the action <math>a
</math>just done by the agent, this is described by the probability distribution of <math>O(o|s',a)
</math>. This state and action is then used to develop a reward <math>r
</math>equal to <math>R(s,a)
</math>. This process then repeats for the next time step until the agent completes its task or to infinity. The goal is for the agent to maximize its expected future discounted reward: <math>E[ \sum_{t=0}^\infty\gamma^tr_t ]
</math>, where <math>r_t
</math>is the reward earned at time <math>t

</math>. <math>\gamma
</math>is the discount factor that determines how much immediate rewards are favoured over distant rewards. When <math>\gamma = 0

</math>the agent only cares about which action will yield the largest expected immediate reward, while if <math>\gamma = 1

</math>the agent cares about maximizing the expected sum of future rewards.

==== Belief Update ====
After executing one time step an agent needs to update its belief of the state of the environment it is in<ref name=":0">Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. “Planning and Acting in Partially Observable Stochastic Domains.” ''Artificial Intelligence'' 101, no. 1–2 (May 1998): 99–134. <nowiki>https://doi.org/10.1016/S0004-3702(98)00023-X</nowiki>.</ref>. Since we assume a ''Markovian'' state space, all we need to describe to execute this step is our prior state belief <math>b</math>, the last action <math>a</math>taken by the agent and the last observation made <math>o</math>. The belief update is an actionless step and is therefore the same as seen on a [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Model] belief update.

The belief state defined as <math>b</math> is a function over all states <math>S</math> from [0,1] that sums up to 1.

The update step can be denoted as <math>b' = \tau(b,a,o)</math>.

After reaching state <math>s'</math>, the agent observes <math>o \in \Omega
</math>with probability <math>O(o|s',a)
</math>as described in the prior section.

If we then let <math>b</math> be a probability distribution over the state space <math>S</math>then <math>b(s)</math>denotes the probability that the environment is in state <math>s</math>. Given <math>b(s)</math>, then after taking an action <math>a</math>and an observation <math>o</math>,

<math display="block">b'(s') = \eta O(o|s',a) \sum_{s \in S} T(s' |s,a)b(s)</math>

where <math>\eta = 1 / Pr(o|b,a)</math> is used as a normalising constant with

<math display="block">Pr(o|b,a) = \sum_{s' \in S} O(o|s',a) \sum_{s \in S} T(s' | s,a)b(s)</math>

==== Interpretation of Definition ====
[[File:DroneSurveilance.gif|thumb|Drone Navigating around space avoiding ground agent using POMDP|439x439px]]
From the above definition the agent does not directly observe its environment. It instead has to make decisions about the true environment state under uncertainty. However, by interacting with the environment and receiving observations the agent is able to update its belief of the true state by updating the probability distribution of the current state. Through this property of the algorithm the extrapolated optimal behaviour may often include actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in future time steps.

If we compare the formal definition of the POMDP described above with that of MDP we would have a very similar structure with the exception that the MDP algorithm would not include the conditional observation probabilities set <math>O</math>as it is always certain of the observed true state.

An example of a POMDP in action can be seen on the left, this animation illustrates a drone (in yellow) navigating a tiled environment. Its objective is to reach the oposing green square without coming into contact with the ground agent (in red). The blue squares represent the drone's observable environment. Since the drone is not capale of observing the state of the ground agent at all times, MDP is not tractable for this task, POMDP enables it to estimate a probability distribution of the likely states the ground agent might be in and act accordingly.

=== Belief MDP ===
A Markovian belief state allows a POMDP to be formulated as an Markov Decision Process where every belief is a state. The resulting belief MDP will be defined on a continuous state space even though the the originating POMDP has a finite number of states. This is because there are infinite number of probability distributions over the state set.

The belief MDP is formally described as a tuple <math>(B,A,\tau ,r ,\gamma )</math>where

<math>B</math>is the set of belief states over the POMDP states

<math>A</math>is the same finite set of actions as in the POMDP algorithm

<math>\tau</math>is the belief state transition function

<math>r: B \times A \rightarrow \R</math>is the reward function on belief states

<math>\gamma</math>is the discount factor equal to the one in the original POMDP

from these values <math>\tau
</math>and <math>r</math>are derived from the original POMDP via

<math display="block">\tau (b,a,b') = \sum_{o \in \Omega} Pr(b'|b,a,o)Pr(o|a,b)</math>

where <math>Pr(o|a,b)</math> is the value derived in the previous section and

<math display="block">Pr(b'|b,a,o) = \begin{cases} 1, & \text{if the belief update with arguments } b,a,o \text{ returns } b' \\ 0, & \text{otherwise} \end{cases}

</math>

and the reward function is the expected reward from the POMDP reward function over the belief distribution as follows

<math display="block">r(b,a) = \sum_{s \in S} b(s)R(s,a)
</math>

By going through these steps the belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP.

This means we were able to take a partially observable discrete space system and convert it to a continuous space fully observable belief system.

[[File:POMDP policy.png|thumb|POMDP decomposed into a state estimator and a policy.]]

=== Policy and Value Function ===
On a Belief MDP the agent is now able to choose between all possible actions to take as it may believe to be in any state with a given probability. We therefore must define a new variable <math>\pi </math>that describes an action <math>a = \pi(b)</math>given a certain belief <math>b</math><ref name=":0" />.

The expected reward for the policy <math>\pi
</math>starting from belief <math>b_0</math>is <math display="block">
V^\pi(b_0) = \sum_{t=0}^\infty \gamma^t r(b_t, a_t) = \sum_{t=0}^\infty \gamma^t E\Bigl[ R(s_t,a_t) \mid b_0, \pi \Bigr]
</math>where again <math>\gamma < 1</math>is the discount factor.

By optimizing for long-term reward we can obtain the optimal policy <math display="block">\pi ^{*}={\underset {\pi }{{\mbox{argmax}}}}\ V^{\pi }(b_{0})</math>where <math>b_0</math>is the initial state.

The optimal value function therefore can be described as

<math display="block">{\displaystyle V^{*}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }\Pr(o\mid b,a)V^{*}(\tau (b,a,o)){\Bigr ]}}</math>

The value function is piecewise linear and convex for a finite-horizon POMDP<ref>Smallwood, R. D., & Sondik, E. J. (1973). ''The Optimal Control of Partially Observable Markov Processes over a Finite Horizon. Operations Research, 21(5), 1071–1088.'' doi:10.1287/opre.21.5.1071 </ref>. For an infinite-horizon POMDP a finite vector set can approximate <math>V^*</math>with the use of dynamic programming techniques.

=== Applications of POMDP ===

==== Pursuit-Evasion ====
Imagine a fleet of robots in a constrained environment, assign one robot to pursuit the others. The pursuer's state is known, but the evader's state is only partially observed. POMDP can be applied by the evaders in a multi-agent search fashion to observe the environment and build a belief of the pursuer's location.<ref>{{Cite journal|last=Hollinger, Singh|first=|date=|title=Efficient Multi-robot Search for a Moving Target|url=https://journals.sagepub.com/doi/10.1177/0278364908099853|journal=The International Journal of Robotics Research|volume=|pages=|via=}}</ref>

==== Sensor Placement ====
A store may have a limited amount of cameras to allocate in its interior to monitor its environment, since the "world " will be partially observable, using POMDP can help reconstruct intruder position or in the contrary facilitate "stealthy" movement.

=== Conclusion ===
Probability theory is a powerful tool for modelling action under uncertainty, thanks to the markov assumption many algorithms have become easy to implement for this purpose. POMDPs are one of the broader algorithms in this category as they take structure from highly constrained algorithms such as MDPs and relax assumptions of observability to allow for more real-world problem solving applications.

== Annotated Bibliography ==
[1] Åström, K.J. “Optimal Control of Markov Processes with Incomplete State Information.” ''Journal of Mathematical Analysis and Applications'' 10, no. 1 (February 1965): 174–205. <nowiki>https://doi.org/10.1016/0022-247X(65)90154-X</nowiki>.

[2] Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. “Planning and Acting in Partially Observable Stochastic Domains.” ''Artificial Intelligence'' 101, no. 1–2 (May 1998): 99–134. <nowiki>https://doi.org/10.1016/S0004-3702(98)00023-X</nowiki>.

[3] Smallwood, R. D., & Sondik, E. J. (1973). ''The Optimal Control of Partially Observable Markov Processes over a Finite Horizon. Operations Research, 21(5), 1071–1088.'' doi:10.1287/opre.21.5.1071

== 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.

File:POMDP policy.png

2020-03-13T20:29:07Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=POMDP decomposed into a state estimator and a policy.}}
|date=2020-03-13
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

[[Category:Computer Science]]
[[Category:Computers and Technology]]

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-13T19:54:06Z

TommasoDAmico:

== Partially Observable Markov Decision Processes (POMDPs) ==
A Partially Observable Markov Decision Processes (POMDs) is a mathematical model for acting under uncertainty. It expands from the Markov Decision Process (MDP) by relaxing the constraint of having a fully observable state space. In this paper we will evaluate the underlying mathematical model and explore the potential of POMDPs for belief MDP.

Principal Author: Tommaso D'Amico

Collaborators: -

== Abstract ==
POMDPs are a type of Decision Network that expands from Markov Decision Processes by not requiring all states to be observable by the agent. POMDPs still maintain the same system dynamics of an MDP although the acting agent cannot always observe its current state but rather it needs to maintain a probability distribution over the set of possible states it may be in based on its observations and the underlying MPD.

=== Builds on ===
POMDPs is a mathematical model expanding from the concepts of [https://wiki.ubc.ca/Course:CPSC522/Decision_Networks Decision networks], specifically generalizing from the [[Course:CPSC522/Markov Decision Processes|Markov Decision Process]] algorithm for acting under uncertainty.

=== Related Pages ===
POMDPs are widely implemented in applications that interact with the real world, some examples are particle filtering techniques such as MC-POMDPs, an extension of [https://wiki.ubc.ca/Course:CPSC522/MCMC Markov Chains Monte Carlo] for POMDPs and [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning]].

POMDPs are also closely related to [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and [https://en.wikipedia.org/wiki/Markov_chain Markov Chains].

== Content ==

=== Introduction ===
Partially Observable Markov Decision Processes (POMDPs) are a type of Markov Process closely related to Markov Decision Processes (MDP) as:
* there exist a finite number of discrete states
* the next state is only determined by the current state and the current action taken by the agent
* there exists a probabilistic transition between states and controllable actions in each state
The way a POMDP differs from an MDP is that the agent is unsure of which state it is in as it has only partial observability of the environment states. It instead needs to develop a probability distribution over the set of states it believes to be in and condition its observations and the underlying MDP structure. A comparison can be drawn for clarity to the relationship of Markov Chains with Hidden Markov Models, as the latter too is an extension of the prior with reduced observability. In fact a helpful illustration of the difference among these models can be seen in the chart below:
{| class="wikitable"
|+'''Helpful Chart for Markov Model Segmentation'''
| colspan="2" rowspan="2" |
| colspan="2" rowspan="1" |'''Does the agent have control over state transition?'''
|-
|no
|yes
|-
| colspan="1" rowspan="2" |'''Are the states fully observable?'''
|yes
|Markov Chain
|Markov Decision Process
|-
|no
|Hidden Markov Model
|Partilly Observable Markov Decision Process
|}

==== POMDP versus MPD ====
MPD is more tractable to solve and is relatively easy to specify although it assumes perfect knowledge of the states which is often unlikely for many use cases.

POMDP on the other hand treats all sources of uncertainty uniformly and allows for information gathering actions, although it is hugely intractable to solve optimally.
=== Formal Definition ===
[[File:POMDP.io.png|thumb|Partially Obsevable Markov Decision Process example (POMDP)|623x623px]]
Formally a POMDP working in discrete-time models the relationship between an agent and its environment<ref>Åström, K.J. “Optimal Control of Markov Processes with Incomplete State Information.” ''Journal of Mathematical Analysis and Applications'' 10, no. 1 (February 1965): 174–205. <nowiki>https://doi.org/10.1016/0022-247X(65)90154-X</nowiki>.</ref>. This is commonly done with a 7-tuple <math>(S,A,T,R,\Omega, O,\gamma)</math>where:
*<math>S</math>is a set of all states
* <math>A
</math>is a set of all actions
* <math>T
</math>is a set that specifies the conditional probability of the next state givent he previous state and action
* <math>R:S \times A\rightarrow \R
</math>is the reward function
* <math>\Omega</math>is the set of observations
* <math>O</math>is the set of conditional observation probabilities
* <math>\gamma \in [0,1]
</math>is the discount factor
At each time step the environment is in state <math>s \in S
</math>. The agent takes action <math>a \in A
</math>, which causes the environment to transition to <math>s'
</math>with probability given by <math>T(s' | s,a).
</math>at the same time the agent receives an observation <math>o \in \Omega
</math>which is dependent on the new environment state <math>s'

</math>and the action <math>a
</math>just done by the agent, this is described by the probability distribution of <math>O(o|s',a)
</math>. This state and action is then used to develop a reward <math>r
</math>equal to <math>R(s,a)
</math>. This process then repeats for the next time step until the agent completes its task or to infinity. The goal is for the agent to maximize its expected future discounted reward: <math>E[ \sum_{t=0}^\infty\gamma^tr_t ]
</math>, where <math>r_t
</math>is the reward earned at time <math>t

</math>. <math>\gamma
</math>is the discount factor that determines how much immediate rewards are favoured over distant rewards. When <math>\gamma = 0

</math>the agent only cares about which action will yield the largest expected immediate reward, while if <math>\gamma = 1

</math>the agent cares about maximizing the expected sum of future rewards.

==== Belief Update ====
After executing one time step an agent needs to update its belief of the state of the environment it is in<ref>Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. “Planning and Acting in Partially Observable Stochastic Domains.” ''Artificial Intelligence'' 101, no. 1–2 (May 1998): 99–134. <nowiki>https://doi.org/10.1016/S0004-3702(98)00023-X</nowiki>.</ref>. Since we assume a ''Markovian'' state space, all we need to describe to execute this step is our prior state belief <math>b</math>, the last action <math>a</math>taken by the agent and the last observation made <math>o</math>.

The belief state defined as <math>b</math> is a function over all states <math>S</math> from [0,1] that sums up to 1.

The update step can be denoted as <math>b' = \tau(b,a,o)</math>.

After reaching state <math>s'</math>, the agent observes <math>o \in \Omega
</math>with probability <math>O(o|s',a)
</math>as described in the prior section.

If we then let <math>b</math> be a probability distribution over the state space <math>S</math>then <math>b(s)</math>denotes the probability that the environment is in state <math>s</math>. Given <math>b(s)</math>, then after taking an action <math>a</math>and an observation <math>o</math>,

<math display="block">b'(s') = \eta O(o|s',a) \sum_{s \in S} T(s' |s,a)b(s)</math>

where <math>\eta = 1 / Pr(o|b,a)</math> is used as a normalising constant with

<math display="block">Pr(o|b,a) = \sum_{s' \in S} O(o|s',a) \sum_{s \in S} T(s' | s,a)b(s)</math>

==== Interpretation of Definition ====
[[File:DroneSurveilance.gif|thumb|Drone Navigating around space avoiding ground agent using POMDP|439x439px]]
From the above definition the agent does not directly observe its environment. It instead has to make decisions about the true environment state under uncertainty. However, by interacting with the environment and receiving observations the agent is able to update its belief of the true state by updating the probability distribution of the current state. Through this property of the algorithm the extrapolated optimal behaviour may often include actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in future time steps.

If we compare the formal definition of the POMDP described above with that of MDP we would have a very similar structure with the exception that the MDP algorithm would not include the conditional observation probabilities set <math>O</math>as it is always certain of the observed true state.

An example of a POMDP in action can be seen on the left, this animation illustrates a drone (in yellow) navigating a tiled environment. Its objective is to reach the oposing green square without coming into contact with the ground agent (in red). The blue squares represent the drone's observable environment. Since the drone is not capale of observing the state of the ground agent at all times, MDP is not tractable for this task, POMDP enables it to estimate a probability distribution of the likely states the ground agent might be in and act accordingly.

=== Belief MDP ===
A Markovian belief state allows a POMDP to be formulated as an Markov Decision Process where every belief is a state. The resulting belief MDP will be defined on a continuous state space even though the the originating POMDP has a finite number of states. This is because there are infinite number of probability distributions over the state set.

The belief MDP is formally described as a tuple <math>(B,A,\tau ,r ,\gamma )</math>where

<math>B</math>is the set of belief states over the POMDP states

<math>A</math>is the same finite set of actions as in the POMDP algorithm

<math>\tau</math>is the belief state transition function

<math>r: B \times A \rightarrow \R</math>is the reward function on belief states

<math>\gamma</math>is the discount factor equal to the one in the original POMDP

from these values <math>\tau
</math>and <math>r</math>are derived from the original POMDP via

<math display="block">\tau (b,a,b') = \sum_{o \in \Omega} Pr(b'|b,a,o)Pr(o|a,b)</math>

where <math>Pr(o|a,b)</math> is the value derived in the previous section and

<math display="block">Pr(b'|b,a,o) = \begin{cases} 1, & \text{if the belief update with arguments } b,a,o \text{ returns } b' \\ 0, & \text{otherwise} \end{cases}

</math>

and the reward function is the expected reward from the POMDP reward function over the belief distribution as follows

<math display="block">r(b,a) = \sum_{s \in S} b(s)R(s,a)
</math>

By going through these steps the belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP.

This means we were able to take a partially observable discrete space system and convert it to a continuous space fully observable belief system.

=== Applications of POMDP ===

==== Pursuit-Evasion ====
Imagine a fleet of robots in a constrained environment, assign one robot to pursuit the others. The pursuer's state is known, but the evader's state is only partially observed. POMDP can be applied by the evaders in a multi-agent search fashion to observe the environment and build a belief of the pursuer's location.<ref>{{Cite journal|last=Hollinger, Singh|first=|date=|title=Efficient Multi-robot Search for a Moving Target|url=https://journals.sagepub.com/doi/10.1177/0278364908099853|journal=The International Journal of Robotics Research|volume=|pages=|via=}}</ref>

==== Sensor Placement ====
A store may have a limited amount of cameras to allocate in its interior to monitor its environment, since the "world " will be partially observable, using POMDP can help reconstruct intruder position or in the contrary facilitate "stealthy" movement.

=== Conclusion ===
Probability theory is a powerful tool for modelling action under uncertainty, thanks to the markov assumption many algorithms have become easy to implement for this purpose. POMDPs are one of the broader algorithms in this category as they take structure from highly constrained algorithms such as MDPs and relax assumptions of observability to allow for more real-world problem solving applications.

== Annotated Bibliography ==
[1] Åström, K.J. “Optimal Control of Markov Processes with Incomplete State Information.” ''Journal of Mathematical Analysis and Applications'' 10, no. 1 (February 1965): 174–205. <nowiki>https://doi.org/10.1016/0022-247X(65)90154-X</nowiki>.

[2] Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. “Planning and Acting in Partially Observable Stochastic Domains.” ''Artificial Intelligence'' 101, no. 1–2 (May 1998): 99–134. <nowiki>https://doi.org/10.1016/S0004-3702(98)00023-X</nowiki>.

== 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.

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-13T19:40:36Z

TommasoDAmico:

== Partially Observable Markov Decision Processes (POMDPs) ==
A Partially Observable Markov Decision Processes (POMDs) is a mathematical model for acting under uncertainty. It expands from the Markov Decision Process (MDP) by relaxing the constraint of having a fully observable state space. In this paper we will evaluate the underlying mathematical model and explore the potential of POMDPs for belief MDP.

Principal Author: Tommaso D'Amico

Collaborators: -

== Abstract ==
POMDPs are a type of Decision Network that expands from Markov Decision Processes by not requiring all states to be observable by the agent. POMDPs still maintain the same system dynamics of an MDP although the acting agent cannot always observe its current state but rather it needs to maintain a probability distribution over the set of possible states it may be in based on its observations and the underlying MPD.

=== Builds on ===
POMDPs is a mathematical model expanding from the concepts of [https://wiki.ubc.ca/Course:CPSC522/Decision_Networks Decision networks], specifically generalizing from the [[Course:CPSC522/Markov Decision Processes|Markov Decision Process]] algorithm for acting under uncertainty.

=== Related Pages ===
POMDPs are widely implemented in applications that interact with the real world, some examples are particle filtering techniques such as MC-POMDPs, an extension of [https://wiki.ubc.ca/Course:CPSC522/MCMC Markov Chains Monte Carlo] for POMDPs and [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning]].

POMDPs are also closely related to [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and [https://en.wikipedia.org/wiki/Markov_chain Markov Chains].

== Content ==

=== Introduction ===
Partially Observable Markov Decision Processes (POMDPs) are a type of Markov Process closely related to Markov Decision Processes (MDP) as:
* there exist a finite number of discrete states
* the next state is only determined by the current state and the current action taken by the agent
* there exists a probabilistic transition between states and controllable actions in each state
The way a POMDP differs from an MDP is that the agent is unsure of which state it is in as it has only partial observability of the environment states. It instead needs to develop a probability distribution over the set of states it believes to be in and condition its observations and the underlying MDP structure. A comparison can be drawn for clarity to the relationship of Markov Chains with Hidden Markov Models, as the latter too is an extension of the prior with reduced observability. In fact a helpful illustration of the difference among these models can be seen in the chart below:
{| class="wikitable"
|+'''Helpful Chart for Markov Model Segmentation'''
| colspan="2" rowspan="2" |
| colspan="2" rowspan="1" |'''Does the agent have control over state transition?'''
|-
|no
|yes
|-
| colspan="1" rowspan="2" |'''Are the states fully observable?'''
|yes
|Markov Chain
|Markov Decision Process
|-
|no
|Hidden Markov Model
|Partilly Observable Markov Decision Process
|}

==== POMDP versus MPD ====
MPD is more tractable to solve and is relatively easy to specify although it assumes perfect knowledge of the states which is often unlikely for many use cases.

POMDP on the other hand treats all sources of uncertainty uniformly and allows for information gathering actions, although it is hugely intractable to solve optimally.
=== Formal Definition ===
[[File:POMDP.io.png|thumb|Partially Obsevable Markov Decision Process example (POMDP)|623x623px]]
Formally a POMDP working in discrete-time models the relationship between an agent and its environment. This is commonly done with a 7-tuple <math>(S,A,T,R,\Omega, O,\gamma)</math>where:
*<math>S</math>is a set of all states
* <math>A
</math>is a set of all actions
* <math>T
</math>is a set that specifies the conditional probability of the next state givent he previous state and action
* <math>R:S \times A\rightarrow \R
</math>is the reward function
* <math>\Omega</math>is the set of observations
* <math>O</math>is the set of conditional observation probabilities
* <math>\gamma \in [0,1]
</math>is the discount factor
At each time step the environment is in state <math>s \in S
</math>. The agent takes action <math>a \in A
</math>, which causes the environment to transition to <math>s'
</math>with probability given by <math>T(s' | s,a).
</math>at the same time the agent receives an observation <math>o \in \Omega
</math>which is dependent on the new environment state <math>s'

</math>and the action <math>a
</math>just done by the agent, this is described by the probability distribution of <math>O(o|s',a)
</math>. This state and action is then used to develop a reward <math>r
</math>equal to <math>R(s,a)
</math>. This process then repeats for the next time step until the agent completes its task or to infinity. The goal is for the agent to maximize its expected future discounted reward: <math>E[ \sum_{t=0}^\infty\gamma^tr_t ]
</math>, where <math>r_t
</math>is the reward earned at time <math>t

</math>. <math>\gamma
</math>is the discount factor that determines how much immediate rewards are favoured over distant rewards. When <math>\gamma = 0

</math>the agent only cares about which action will yield the largest expected immediate reward, while if <math>\gamma = 1

</math>the agent cares about maximizing the expected sum of future rewards.

==== Belief Update ====
after executing one time step an agent needs to update its belief of the state of the environment it is in. Since we assume a ''Markovian'' state space, all we need to describe to execute this step is our prior state belief <math>b</math>, the last action <math>a</math>taken by the agent and the last observation made <math>o</math>.

The update step can be denoted as <math>b' = \tau(b,a,o)</math>.

After reaching state <math>s'</math>, the agent observes <math>o \in \Omega
</math>with probability <math>O(o|s',a)
</math>as described in the prior section.

If we then let <math>b</math> be a probability distribution over the state space <math>S</math>then <math>b(s)</math>denotes the probability that the environment is in state <math>s</math>. Given <math>b(s)</math>, then after taking an action <math>a</math>and an observation <math>o</math>,

<math display="block">b'(s') = \eta O(o|s',a) \sum_{s \in S} T(s' |s,a)b(s)</math>

where <math>\eta = 1 / Pr(o|b,a)</math> is used as a normalising constant with

<math display="block">Pr(o|b,a) = \sum_{s' \in S} O(o|s',a) \sum_{s \in S} T(s' | s,a)b(s)</math>

==== Interpretation of Definition ====
[[File:DroneSurveilance.gif|thumb|Drone Navigating around space avoiding ground agent using POMDP|443x443px]]
From the above definition the agent does not directly observe its environment. It instead has to make decisions about the true environment state under uncertainty. However, by interacting with the environment and receiving observations the agent is able to update its belief of the true state by updating the probability distribution of the current state. Through this property of the algorithm the extrapolated optimal behaviour may often include actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in future time steps.

If we compare the formal definition of the POMDP described above with that of MDP we would have a very similar structure with the exception that the MDP algorithm would not include the conditional observation probabilities set <math>O</math>as it is always certain of the observed true state.

An example of a POMDP in action can be seen on the left, this animation illustrates a drone (in yellow) navigating a tiled environment. Its objective is to reach the oposing green square without coming into contact with the ground agent (in red). The blue squares represent the drone's observable environment. Since the drone is not capale of observing the state of the ground agent at all times, MDP is not tractable for this task, POMDP enables it to estimate a probability distribution of the likely states the ground agent might be in and act accordingly.

=== Belief MDP ===
A Markovian belief state allows a POMDP to be formulated as an Markov Decision Process where every belief is a state. The resulting belief MDP will thus be defined on a continuous state space even though the the originating POMDP has a finite number of states. This is because there are infinite number of probability distributions over the state set.

The belief MDP is formally described as a tuple <math>(B,A,\tau ,r ,\gamma )</math>where

<math>B</math>is the set of belief states over the POMDP states

<math>A</math>is the same finite set of actions as in the POMDP algorithm

<math>\tau</math>is the belief state transition function

<math>r: B \times A \rightarrow \R</math>is the reward function on belief states

<math>\gamma</math>is the discount factor equal to the one in the original POMDP

from these values <math>\tau
</math>and <math>r</math>are derived from the oroginal POMDP via

<math display="block">\tau (b,a,b') = \sum_{o \in \Omega} Pr(b'|b,a,o)Pr(o|a,b)</math>

where <math>Pr(o|a,b)</math> is the value derived in the previous section and

<math display="block">Pr(b'|b,a,o) = \begin{cases} 1, & \text{if the belief update with arguments } b,a,o \text{ returns } b' \\ 0, & \text{otherwise} \end{cases}

</math>

and the reward function is the expected reward from the POMDP reward function over the belief distribution as follows

<math display="block">r(b,a) = \sum_{s \in S} b(s)R(s,a)
</math>

By going through these steps the belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP.

This means we were able to take a partially observable discrete space system and convert it to a continuous space fully observable belief system.

=== Applications of POMDP ===

==== Pursuit-Evasion ====
Imagine a fleet of robots in a constrained environment, assign one robot to pursuit the others. The pursuer's state is known, but the evader's state is only partially observed. POMDP can be applied by the evaders in a multi-agent search fashion to observe the environment and build a belief of the pursuer's location.<ref>{{Cite journal|last=Hollinger, Singh|first=|date=|title=Efficient Multi-robot Search for a Moving Target|url=https://journals.sagepub.com/doi/10.1177/0278364908099853|journal=The International Journal of Robotics Research|volume=|pages=|via=}}</ref>

==== Sensor Placement ====
A store may have a limited amount of cameras to allocate in its interior to monitor its environment, since the "world " will be partially observable, using POMDP can help reconstruct intruder position or in the contrary facilitate "stealthy" movement.

=== Conclusion ===
Probability theory is a powerful tool for modelling action under uncertainty, thanks to the markov assumption many algorithms have become easy to implement for this purpose. POMDPs are one of the broader algorithms in this category as they take structure from highly constrained algorithms such as MDPs and relax assumptions of observability to allow for more real-world problem solving applications.

== Annotated Bibliography ==
[1] Åström, K.J. “Optimal Control of Markov Processes with Incomplete State Information.” ''Journal of Mathematical Analysis and Applications'' 10, no. 1 (February 1965): 174–205. <nowiki>https://doi.org/10.1016/0022-247X(65)90154-X</nowiki>.

[2] Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. “Planning and Acting in Partially Observable Stochastic Domains.” ''Artificial Intelligence'' 101, no. 1–2 (May 1998): 99–134. <nowiki>https://doi.org/10.1016/S0004-3702(98)00023-X</nowiki>.

== 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.

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-13T19:23:20Z

TommasoDAmico:

== Partially Observable Markov Decision Processes (POMDPs) ==
A Partially Observable Markov Decision Processes (POMDs) is a mathematical model for acting under uncertainty. It expands from the Markov Decision Process (MDP) by relaxing the constraint of having a fully observable state space. In this paper we will evaluate the underlying mathematical model and explore the potential of POMDPs for belief MDP.

Principal Author: Tommaso D'Amico
[[File:DroneSurveilance.gif|thumb|Drone Navigating around space avoiding ground agent using POMDP]]
Collaborators: -

== Abstract ==
POMDPs are a type of Decision Network that expands from Markov Decision Processes by not requiring all states to be observable by the agent. POMDPs still maintain the same system dynamics of an MDP although the acting agent cannot always observe its current state but rather it needs to maintain a probability distribution over the set of possible states it may be in based on its observations and the underlying MPD.

=== Builds on ===
POMDPs is a mathematical model expanding from the concepts of [https://wiki.ubc.ca/Course:CPSC522/Decision_Networks Decision networks], specifically generalizing from the [[Course:CPSC522/Markov Decision Processes|Markov Decision Process]] algorithm for acting under uncertainty.

=== Related Pages ===
POMDPs are widely implemented in applications that interact with the real world, some examples are particle filtering techniques such as MC-POMDPs, an extension of [https://wiki.ubc.ca/Course:CPSC522/MCMC Markov Chains Monte Carlo] for POMDPs and [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning]].

POMDPs are also closely related to [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and [https://en.wikipedia.org/wiki/Markov_chain Markov Chains].

== Content ==

=== Introduction ===
[[File:POMDP.io.png|thumb|Partially Obsevable Markov Decision Process example (POMDP)]]
Partially Observable Markov Decision Processes (POMDPs) are a type of Markov Process closely related to Markov Decision Processes (MDP) as:
* there exist a finite number of discrete states
* the next state is only determined by the current state and the current action taken by the agent
* there exists a probabilistic transition between states and controllable actions in each state
The way a POMDP differs from an MDP is that the agent is unsure of which state it is in as it has only partial observability of the environment states. It instead needs to develop a probability distribution over the set of states it believes to be in and condition its observations and the underlying MDP structure. A comparison can be drawn for clarity to the relationship of Markov Chains with Hidden Markov Models, as the latter too is an extension of the prior with reduced observability. In fact a helpful illustration of the difference among these models can be seen in the chart below:
{| class="wikitable"
|+'''Helpful Chart for Markov Model Segmentation'''
| colspan="2" rowspan="2" |
| colspan="2" rowspan="1" |'''Does the agent have control over state transition?'''
|-
|no
|yes
|-
| colspan="1" rowspan="2" |'''Are the states fully observable?'''
|yes
|Markov Chain
|Markov Decision Process
|-
|no
|Hidden Markov Model
|Partilly Observable Markov Decision Process
|}

==== POMDP versus MPD ====
MPD is more tractable to solve and is relatively easy to specify although it assumes perfect knowledge of the states which is often unlikely for many use cases.

POMDP on the other hand treats all sources of uncertainty uniformly and allows for information gathering actions, although it is hugely intractable to solve optimally.
=== Formal Definition ===
Formally a POMDP working in discrete-time models the relationship between an agent and its environment. This is commonly done with a 7-tuple <math>(S,A,T,R,\Omega, O,\gamma)</math>where:
* <math>S</math>is a set of all states
* <math>A
</math>is a set of all actions
* <math>T
</math>is a set that specifies the conditional probability of the next state givent he previous state and action
* <math>R:S \times A\rightarrow \R
</math>is the reward function
* <math>\Omega</math>is the set of observations
* <math>O</math>is the set of conditional observation probabilities
* <math>\gamma \in [0,1]
</math>is the discount factor
At each time step the environment is in state <math>s \in S
</math>. The agent takes action <math>a \in A
</math>, which causes the environment to transition to <math>s'
</math>with probability given by <math>T(s' | s,a).
</math>at the same time the agent receives an observation <math>o \in \Omega
</math>which is dependent on the new environment state <math>s'

</math>and the action <math>a
</math>just done by the agent, this is described by the probability distribution of <math>O(o|s',a)
</math>. This state and action is then used to develop a reward <math>r
</math>equal to <math>R(s,a)
</math>. This process then repeats for the next time step until the agent completes its task or to infinity. The goal is for the agent to maximize its expected future discounted reward: <math>E[ \sum_{t=0}^\infty\gamma^tr_t ]
</math>, where <math>r_t
</math>is the reward earned at time <math>t

</math>. <math>\gamma
</math>is the discount factor that determines how much immediate rewards are favoured over distant rewards. When <math>\gamma = 0

</math>the agent only cares about which action will yield the largest expected immediate reward, while if <math>\gamma = 1

</math>the agent cares about maximizing the expected sum of future rewards.

==== Belief Update ====
after executing one time step an agent needs to update its belief of the state of the environment it is in. Since we assume a ''Markovian'' state space, all we need to describe to execute this step is our prior state belief <math>b</math>, the last action <math>a</math>taken by the agent and the last observation made <math>o</math>.

The update step can be denoted as <math>b' = \tau(b,a,o)</math>.

After reaching state <math>s'</math>, the agent observes <math>o \in \Omega
</math>with probability <math>O(o|s',a)
</math>as described in the prior section.

If we then let <math>b</math> be a probability distribution over the state space <math>S</math>then <math>b(s)</math>denotes the probability that the environment is in state <math>s</math>. Given <math>b(s)</math>, then after taking an action <math>a</math>and an observation <math>o</math>,

<math>b'(s') = \eta O(o|s',a) \sum_{s \in S} T(s' |s,a)b(s)</math>

where <math>\eta = 1 / Pr(o|b,a)</math> is used as a normalising constant with

<math>Pr(o|b,a) = \sum_{s' \in S} O(o|s',a) \sum_{s \in S} T(s' | s,a)b(s)</math>

==== Interpretation of Definition ====
From the above definition the agent does not directly observe its environment. It instead has to make decisions about the true environment state under uncertainty. However, by interacting with the environment and receiving observations the agent is able to update its belief of the true state by updating the probability distribution of the current state. Through this property of the algorithm the extrapolated optimal behaviour may often include actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in future time steps.

If we compare the formal definition of the POMDP described above with that of MDP we would have a very similar structure with the exception that the MDP algorithm would not include the conditional observation probabilities set <math>O</math>as it is always certain of the observed true state.

=== Belief MDP ===
A Markovian belief state allows a POMDP to be formulated as an Markov Decision Process where every belief is a state. The resulting belief MDP will thus be defined on a continuous state space even though the the originating POMDP has a finite number of states. This is because there are infinite number of probability distributions over the state set.

The belief MDP is formally described as a tuple <math>(B,A,\tau ,r ,\gamma )</math>where

<math>B</math>is the set of belief states over the POMDP states

<math>A</math>is the same finite set of actions as in the POMDP algorithm

<math>\tau</math>is the belief state transition function

<math>r: B \times A \rightarrow \R</math>is the reward function on belief states

<math>\gamma</math>is the discount factor equal to the one in the original POMDP

from these values <math>\tau
</math>and <math>r</math>are derived from the oroginal POMDP via

<math>\tau (b,a,b') = \sum_{o \in \Omega} Pr(b'|b,a,o)Pr(o|a,b)</math>

where <math>Pr(o|a,b)</math> is the value derived in the previous section and

<math>Pr(b'|b,a,o) = \begin{cases} 1, & \text{if the belief update with arguments } b,a,o \text{ returns } b' \\ 0, & \text{otherwise} \end{cases}

</math>

and the reward function is the expected reward from the POMDP reward function over the belief distribution as follows <math>r(b,a) = \sum_{s \in S} b(s)R(s,a)
</math>

By going through these steps the belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP.

This means we were able to take a partially observable discrete space system and convert it to a continuous space fully observable belief system.

=== Applications of POMDP ===

==== Pursuit-Evasion ====
Imagine a fleet of robots in a constrained environment, assign one robot to pursuit the others. The pursuer's state is known, but the evader's state is only partially observed. POMDP can be applied by the evaders in a multi-agent search fashion to observe the environment and build a belief of the pursuer's location.<ref>{{Cite journal|last=Hollinger, Singh|first=|date=|title=Efficient Multi-robot Search for a Moving Target|url=https://journals.sagepub.com/doi/10.1177/0278364908099853|journal=The International Journal of Robotics Research|volume=|pages=|via=}}</ref>

==== Sensor Placement ====
A store may have a limited amount of cameras to allocate in its interior to monitor its environment, since the "world " will be partially observable, using POMDP can help reconstruct intruder position or in the contrary facilitate "stealthy" movement.

=== Conclusion ===
Probability theory is a powerful tool for modelling action under uncertainty, thanks to the markov assumption many algorithms have become easy to implement for this purpose. POMDPs are one of the broader algorithms in this category as they take structure from highly constrained algorithms such as MDPs and relax assumptions of observability to allow for more real-world problem solving applications.

== Annotated Bibliography ==
[1] Hansen, Eric A, Daniel S Bernstein, and Shlomo Zilberstein. “Dynamic Programming for Partially Observable Stochastic Games,” n.d., 6.

[2]G. Hollinger, S. Singh, J. Djugash, and A. Kehagias, “Efficient Multi-robot Search for a Moving Target,” The International Journal of Robotics Research, vol. 28, no. 2, pp. 201–219, Feb. 2009, doi: 10.1177/0278364908099853.

== 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.

File:DroneSurveilance.gif

2020-03-13T19:10:41Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Drone Navigating around space avoiding ground agent using POMDP}}
|date=2020-03-13
|source=https://juliaobserver.com/packages/POMDPGallery
|author= M. Svoreňová, M. Chmelík, K. Leahy, H. F. Eniser, K. Chatterjee, I. Černá, C. Belta
|permission=
|other versions=
}}

=={{int:license-header}}==
{{cc-by-sa-4.0}}

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-13T18:50:43Z

TommasoDAmico:

== Partially Observable Markov Decision Processes (POMDPs) ==
A Partially Observable Markov Decision Processes (POMDs) is a mathematical model for acting under uncertainty. It expands from the Markov Decision Process (MDP) by relaxing the constraint of having a fully observable state space. In this paper we will evaluate the underlying mathematical model and explore the potential of POMDPs for belief MDP.

Principal Author: Tommaso D'Amico

Collaborators: -

== Abstract ==
POMDPs are a type of Decision Network that expands from Markov Decision Processes by not requiring all states to be observable by the agent. POMDPs still maintain the same system dynamics of an MDP although the acting agent cannot always observe its current state but rather it needs to maintain a probability distribution over the set of possible states it may be in based on its observations and the underlying MPD.

=== Builds on ===
POMDPs is a mathematical model expanding from the concepts of [https://wiki.ubc.ca/Course:CPSC522/Decision_Networks Decision networks], specifically generalizing from the [[Course:CPSC522/Markov Decision Processes|Markov Decision Process]] algorithm for acting under uncertainty.

=== Related Pages ===
POMDPs are widely implemented in applications that interact with the real world, some examples are particle filtering techniques such as MC-POMDPs, an extension of [https://wiki.ubc.ca/Course:CPSC522/MCMC Markov Chains Monte Carlo] for POMDPs and [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning]].

POMDPs are also closely related to [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and [https://en.wikipedia.org/wiki/Markov_chain Markov Chains].

== Content ==

=== Introduction ===
[[File:POMDP.io.png|thumb|Partially Obsevable Markov Decision Process example (POMDP)]]
Partially Observable Markov Decision Processes (POMDPs) are a type of Markov Process closely related to Markov Decision Processes (MDP) as:
* there exist a finite number of discrete states
* the next state is only determined by the current state and the current action taken by the agent
* there exists a probabilistic transition between states and controllable actions in each state
The way a POMDP differs from an MDP is that the agent is unsure of which state it is in as it has only partial observability of the environment states. It instead needs to develop a probability distribution over the set of states it believes to be in and condition its observations and the underlying MDP structure. A comparison can be drawn for clarity to the relationship of Markov Chains with Hidden Markov Models, as the latter too is an extension of the prior with reduced observability. In fact a helpful illustration of the difference among these models can be seen in the chart below:
{| class="wikitable"
|+'''Helpful Chart for Markov Model Segmentation'''
| colspan="2" rowspan="2" |
| colspan="2" rowspan="1" |'''Does the agent have control over state transition?'''
|-
|no
|yes
|-
| colspan="1" rowspan="2" |'''Are the states fully observable?'''
|yes
|Markov Chain
|Markov Decision Process
|-
|no
|Hidden Markov Model
|Partilly Observable Markov Decision Process
|}

==== POMDP versus MPD ====
MPD is more tractable to solve and is relatively easy to specify although it assumes perfect knowledge of the states which is often unlikely for many use cases.

POMDP on the other hand treats all sources of uncertainty uniformly and allows for information gathering actions, although it is hugely intractable to solve optimally.
=== Formal Definition ===
Formally a POMDP working in discrete-time models the relationship between an agent and its environment. This is commonly done with a 7-tuple <math>(S,A,T,R,\Omega, O,\gamma)</math>where:
* <math>S</math>is a set of all states
* <math>A
</math>is a set of all actions
* <math>T
</math>is a set that specifies the conditional probability of the next state givent he previous state and action
* <math>R:S \times A\rightarrow \R
</math>is the reward function
* <math>\Omega</math>is the set of observations
* <math>O</math>is the set of conditional observation probabilities
* <math>\gamma \in [0,1]
</math>is the discount factor
At each time step the environment is in state <math>s \in S
</math>. The agent takes action <math>a \in A
</math>, which causes the environment to transition to <math>s'
</math>with probability given by <math>T(s' | s,a).
</math>at the same time the agent receives an observation <math>o \in \Omega
</math>which is dependent on the new environment state <math>s'

</math>and the action <math>a
</math>just done by the agent, this is described by the probability distribution of <math>O(o|s',a)
</math>. This state and action is then used to develop a reward <math>r
</math>equal to <math>R(s,a)
</math>. This process then repeats for the next time step until the agent completes its task or to infinity. The goal is for the agent to maximize its expected future discounted reward: <math>E[ \sum_{t=0}^\infty\gamma^tr_t ]
</math>, where <math>r_t
</math>is the reward earned at time <math>t

</math>. <math>\gamma
</math>is the discount factor that determines how much immediate rewards are favoured over distant rewards. When <math>\gamma = 0

</math>the agent only cares about which action will yield the largest expected immediate reward, while if <math>\gamma = 1

</math>the agent cares about maximizing the expected sum of future rewards.

==== Belief Update ====
after executing one time step an agent needs to update its belief of the state of the environment it is in. Since we assume a ''Markovian'' state space, all we need to describe to execute this step is our prior state belief <math>b</math>, the last action <math>a</math>taken by the agent and the last observation made <math>o</math>.

The update step can be denoted as <math>b' = \tau(b,a,o)</math>.

After reaching state <math>s'</math>, the agent observes <math>o \in \Omega
</math>with probability <math>O(o|s',a)
</math>as described in the prior section.

If we then let <math>b</math> be a probability distribution over the state space <math>S</math>then <math>b(s)</math>denotes the probability that the environment is in state <math>s</math>. Given <math>b(s)</math>, then after taking an action <math>a</math>and an observation <math>o</math>,

<math>b'(s') = \eta O(o|s',a) \sum_{s \in S} T(s' |s,a)b(s)</math>

where <math>\eta = 1 / Pr(o|b,a)</math> is used as a normalising constant with

<math>Pr(o|b,a) = \sum_{s' \in S} O(o|s',a) \sum_{s \in S} T(s' | s,a)b(s)</math>

==== Interpretation of Definition ====
From the above definition the agent does not directly observe its environment. It instead has to make decisions about the true environment state under uncertainty. However, by interacting with the environment and receiving observations the agent is able to update its belief of the true state by updating the probability distribution of the current state. Through this property of the algorithm the extrapolated optimal behaviour may often include actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in future time steps.

If we compare the formal definition of the POMDP described above with that of MDP we would have a very similar structure with the exception that the MDP algorithm would not include the conditional observation probabilities set <math>O</math>as it is always certain of the observed true state.

=== Belief MDP ===
A Markovian belief state allows a POMDP to be formulated as an Markov Decision Process where every belief is a state. The resulting belief MDP will thus be defined on a continuous state space even though the the originating POMDP has a finite number of states. This is because there are infinite number of probability distributions over the state set.

The belief MDP is formally described as a tuple <math>(B,A,\tau ,r ,\gamma )</math>where

<math>B</math>is the set of belief states over the POMDP states

<math>A</math>is the same finite set of actions as in the POMDP algorithm

<math>\tau</math>is the belief state transition function

<math>r: B \times A \rightarrow \R</math>is the reward function on belief states

<math>\gamma</math>is the discount factor equal to the one in the original POMDP

from these values <math>\tau
</math>and <math>r</math>are derived from the oroginal POMDP via

<math>\tau (b,a,b') = \sum_{o \in \Omega} Pr(b'|b,a,o)Pr(o|a,b)</math>

where <math>Pr(o|a,b)</math> is the value derived in the previous section and

<math>Pr(b'|b,a,o) = \begin{cases} 1, & \text{if the belief update with arguments } b,a,o \text{ returns } b' \\ 0, & \text{otherwise} \end{cases}

</math>

and the reward function is the expected reward from the POMDP reward function over the belief distribution as follows <math>r(b,a) = \sum_{s \in S} b(s)R(s,a)
</math>

By going through these steps the belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP.

This means we were able to take a partially observable discrete space system and convert it to a continuous space fully observable belief system.

=== Applications of POMDP ===

==== Pursuit-Evasion ====
Imagine a fleet of robots in a constrained environment, assign one robot to pursuit the others. The pursuer's state is known, but the evader's state is only partially observed. POMDP can be applied by the evaders in a multi-agent search fashion to observe the environment and build a belief of the pursuer's location.<ref>{{Cite journal|last=Hollinger, Singh|first=|date=|title=Efficient Multi-robot Search for a Moving Target|url=https://journals.sagepub.com/doi/10.1177/0278364908099853|journal=The International Journal of Robotics Research|volume=|pages=|via=}}</ref>

==== Sensor Placement ====
A store may have a limited amount of cameras to allocate in its interior to monitor its environment, since the "world " will be partially observable, using POMDP can help reconstruct intruder position or in the contrary facilitate "stealthy" movement.

=== Conclusion ===
Probability theory is a powerful tool for modelling action under uncertainty, thanks to the markov assumption many algorithms have become easy to implement for this purpose. POMDPs are one of the broader algorithms in this category as they take structure from highly constrained algorithms such as MDPs and relax assumptions of observability to allow for more real-world problem solving applications.

== Annotated Bibliography ==
[1] Hansen, Eric A, Daniel S Bernstein, and Shlomo Zilberstein. “Dynamic Programming for Partially Observable Stochastic Games,” n.d., 6.

[2]G. Hollinger, S. Singh, J. Djugash, and A. Kehagias, “Efficient Multi-robot Search for a Moving Target,” The International Journal of Robotics Research, vol. 28, no. 2, pp. 201–219, Feb. 2009, doi: 10.1177/0278364908099853.

== 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.

File:POMDP.io.png

2020-03-13T18:39:49Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=Partially Obsevable Markov Decision Process example (POMDP)}}
|date=2020-03-13
|source={{own}}
|author=[[User:TommasoDAmico|TommasoDAmico]]
|permission=
|other versions=
}}

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

[[Category:Computer Science]]

Thread:Course talk:CPSC522/Conditional GANs for Image to Image Translation/peer feedback

2020-03-10T01:59:51Z

TommasoDAmico:

I really enjoyed reading about this topic!

The examples are quite nice to show its capabilities,

It would make it a bit clearer if you wrote the variables in latex when describing the objective function.

I would like to perhaps know a bit more about the advantages and disadvantages of this algorithm, I found the last few paragraphs a bit confusing in their structure.

(5) The topic is relevant for the course.

(4) 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).

(4) The formalism (definitions, mathematics) was well chosen to make the page easier to understand.

(5) The abstract is a concise and clear summary.

(5) There were appropriate (original) examples that helped make the topic clear.

(-) There was appropriate use of (pseudo-) code.

(4) It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic).

(5) 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.

(5) The references and links to external pages are well chosen.

(5) 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.

Thread:Course talk:CPSC522/Conditional GANs for Image to Image Translation/peer feedback

2020-03-10T01:59:13Z

TommasoDAmico: New thread: peer feedback

I really enjoyed reading about this topic!
The examples are quite nice to show its capabilities,
It would make it a bit clearer if you wrote the variables in latex when describing the objective function.
I would like to perhaps know a bit more about the advantages and disadvantages of this algorithm, I found the last few paragraphs a bit confusing in their structure.

(5) The topic is relevant for the course.

(4) 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).

(4) The formalism (definitions, mathematics) was well chosen to make the page easier to understand.

(5) The abstract is a concise and clear summary.

(5) There were appropriate (original) examples that helped make the topic clear.

(-) There was appropriate use of (pseudo-) code.

(4) It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic).

(5) 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.

(5) The references and links to external pages are well chosen.

(5) 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.

Thread:Course talk:CPSC 522/Progressive Neural Network/Peer Feedback

2020-03-10T01:25:17Z

TommasoDAmico: New thread: Peer Feedback

Your page is well structured and the concepts presented are well introduced. I'd rephrase some parts of the introduction to make it easier to read.
for example "This paper will give a short overview of continual learning and the different approaches used in literature to achieve it. The paper will then explore one of these methods, progressive neural networks."
maybe something of this kind: "This paper will provide a short overview of continual learning and the different approaches used, diving more into detail in the progressive neural networks method."
It seems as if you are yet to finish your page. I'd like to maybe have some examples of applications of the algorithm or where it is been used.
I liked your graph, it was very relevant and helpful to my comprehension.

(5) The topic is relevant for the course.

(4) 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).

(4) The formalism (definitions, mathematics) was well chosen to make the page easier to understand.

(5) 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.

(4) It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic).

(5) 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.

(5) The references and links to external pages are well chosen.

(5) 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.

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-02T21:37:22Z

TommasoDAmico:

== Partially Observable Markov Decision Processes (POMDPs) ==
A Partially Observable Markov Decision Processes (POMDs) is a mathematical model for acting under uncertainty. It expands from the Markov Decision Process (MDP) by relaxing the constraint of having a fully observable state space. In this paper we will evaluate the underlying mathematical model and explore the potential of POMDPs for belief MDP.

Principal Author: Tommaso D'Amico

Collaborators: -

== Abstract ==
POMDPs are a type of Decision Network that expands from Markov Decision Processes by not requiring all states to be observable by the agent. POMDPs still maintain the same system dynamics of an MDP although the acting agent cannot always observe its current state but rather it needs to maintain a probability distribution over the set of possible states it may be in based on its observations and the underlying MPD.

=== Builds on ===
POMDPs is a mathematical model expanding from the concepts of [https://wiki.ubc.ca/Course:CPSC522/Decision_Networks Decision networks], specifically generalizing from the [[Course:CPSC522/Markov Decision Processes|Markov Decision Process]] algorithm for acting under uncertainty.

=== Related Pages ===
POMDPs are widely implemented in applications that interact with the real world, some examples are particle filtering techniques such as MC-POMDPs, an extension of [https://wiki.ubc.ca/Course:CPSC522/MCMC Markov Chains Monte Carlo] for POMDPs, [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning]] and game logic with Partially Observable Stochastic Games (POSG)<ref>Hansen, Eric A, Daniel S Bernstein, and Shlomo Zilberstein. “Dynamic Programming for Partially Observable Stochastic Games,” n.d., 6.</ref>.

POMDPs are also closely related to [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and [https://en.wikipedia.org/wiki/Markov_chain Markov Chains].

== Content ==

=== Introduction ===
[[File:State Machine illustration.jpg|thumb|POMDP Example with two states s1,s2 and two actions a1 and a2]]
Partially Observable Markov Decision Processes (POMDPs) are a type of Markov Process closely related to Markov Decision Processes (MDP) as:
* there exist a finite number of discrete states
* the next state is only determined by the current state and the current action taken by the agent
* there exists a probabilistic transition between states and controllable actions in each state
The way a POMDP differs from an MDP is that the agent is unsure of which state it is in as it has only partial observability of the environment states. It instead needs to develop a probability distribution over the set of states it believes to be in and condition its observations and the underlying MDP structure. A comparison can be drawn for clarity to the relationship of Markov Chains with Hidden Markov Models, as the latter too is an extension of the prior with reduced observability. In fact a helpful illustration of the difference among these models can be seen in the chart below:
{| class="wikitable"
|+'''Helpful Chart for Markov Model Segmentation'''
| colspan="2" rowspan="2" |
| colspan="2" rowspan="1" |'''Does the agent have control over state transition?'''
|-
|no
|yes
|-
| colspan="1" rowspan="2" |'''Are the states fully observable?'''
|yes
|Markov Chain
|MDP
|-
|no
|HMM
|POMDPs
|}

==== POMDP versus MPD ====
MPD is more tractable to solve and is relatively easy to specify although it assumes perfect knowledge of the states which is often unlikely for many use cases.

POMDP on the other hand treats all sources of uncertainty uniformly and allows for information gathering actions, although it is hugely intractable to solve optimally.

=== Formal Definition ===
Formally a POMDP working in discrete-time models the relationship between an agent and its environment. This is commonly done with a 7-tuple <math>(S,A,T,R,\Omega, O,\gamma)</math>where:
* <math>S</math>is a set of all states
* <math>A
</math>is a set of all actions
* <math>T
</math>is a set of conditional transition probabilities between states
* <math>R:S \times A\rightarrow \R
</math>is the reward function
* <math>\Omega</math>is the set of observations
* <math>O</math>is the set of conditional observation probabilities
* <math>\gamma \in [0,1]
</math>is the discount factor
At each time step the environment is in state <math>s \in S
</math>. The agent takes action <math>a \in A
</math>, which causes the environment to transition to <math>s'
</math>with probability given by <math>T(s' | s,a).
</math>at the same time the agent receives an observation <math>o \in \Omega
</math>which is dependent on the new environment state <math>s'

</math>and the action <math>a
</math>just done by the agent, this is described by the probability distribution of <math>O(o|s',a)
</math>. This state and action is then used to develop a reward <math>r
</math>equal to <math>R(s,a)
</math>. This process then repeats for the next time step until the agent completes its task or to infinity. The goal is for the agent to maximize its expected future discounted reward: <math>E[ \sum_{t=0}^\inf\gamma^tr_t ]
</math>, where <math>r_t
</math>is the reward earned at time <math>t

</math>. <math>\gamma
</math>is the discount factor that determines how much immediate rewards are favoured over distant rewards. When <math>\gamma = 0

</math>the agent only cares about which action will yield the largest expected immediate reward, while if <math>\gamma = 1

</math>the agent cares about maximizing the expected sum of future rewards.

==== Belief Update ====
after executing one time step an agent needs to update its belief of the state of the environment it is in. Since we assume a ''Markovian'' state space, all we need to describe to execute this step is our prior state belief <math>b</math>, the last action <math>a</math>taken by the agent and the last observation made <math>o</math>.

The update step can be denoted as <math>b' = \tau(b,a,o)</math>.

After reaching state <math>s'</math>, the agent observes <math>o \in \Omega
</math>with probability <math>O(o|s',a)
</math>as described in the prior section.

If we then let <math>b</math> be a probability distribution over the state space <math>S</math>then <math>b(s)</math>denotes the probability that the environment is in state <math>s</math>. Given <math>b(s)</math>, then after taking an action <math>a</math>and an observation <math>o</math>,

<math>b'(s') = \eta O(o|s',a) \sum_{s \in S} T(s' |s,a)b(s)</math>

where <math>\eta = 1 / Pr(o|b,a)</math> is used as a normalising constant with

<math>Pr(o|b,a) = \sum_{s' \in S} O(o|s',a) \sum_{s \in S} T(s' | s,a)b(s)</math>

==== Interpretation of Definition ====
From the above definition the agent does not directly observe its environment. It instead has to make decisions about the true environment state under uncertainty. However, by interacting with the environment and receiving observations the agent is able to update its belief of the true state by updating the probability distribution of the current state. Through this property of the algorithm the extrapolated optimal behaviour may often include actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in future time steps.

If we compare the formal definition of the POMDP described above with that of MDP we would have a very similar structure with the exception that the MDP algorithm would not include the conditional observation probabilities set <math>O</math>as it is always certain of the observed true state.

=== Belief MDP ===
A Markovian belief state allows a POMDP to be formulated as an Markov Decision Process where every belief is a state. The resulting belief MDP will thus be defined on a continuous state space even though the the originating POMDP has a finite number of states. This is because there are infinite number of probability distributions over the state set.

The belief MDP is formally described as a tuple <math>(B,A,\tau ,r ,\gamma )</math>where

<math>B</math>is the set of belief states over the POMDP states

<math>A</math>is the same finite set of actions as in the POMDP algorithm

<math>\tau</math>is the belief state transition function

<math>r: B \times A \rightarrow \R</math>is the reward function on belief states

<math>\gamma</math>is the discount factor equal to the one in the original POMDP

from these values <math>\tau
</math>and <math>r</math>are derived from the oroginal POMDP via

<math>\tau (b,a,b') = \sum_{o \in \Omega} Pr(b'|b,a,o)Pr(o|a,b)</math>

where <math>Pr(o|a,b)</math> is the value derived in the previous section and

<math>Pr(b'|b,a,o) = \begin{cases} 1, & \text{if the belief update with arguments } b,a,o \text{ returns } b' \\ 0, & \text{otherwise} \end{cases}

</math>

and the reward function is the expected reward from the POMDP reward function over the belief distribution as follows <math>r(b,a) = \sum_{s \in S} b(s)R(s,a)
</math>

By going through these steps the belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP.

This means we were able to take a partially observable discrete space system and convert it to a continuous space fully observable belief system.

=== Applications of POMDP ===

==== Pursuit-Evasion ====
Imagine a fleet of robots in a constrained environment, assign one robot to pursuit the others. The pursuer's state is known, but the evader's state is only partially observed. POMDP can be applied by the evaders in a multi-agent search fashion to observe the environment and build a belief of the pursuer's location.<ref>{{Cite journal|last=Hollinger, Singh|first=|date=|title=Efficient Multi-robot Search for a Moving Target|url=https://journals.sagepub.com/doi/10.1177/0278364908099853|journal=The International Journal of Robotics Research|volume=|pages=|via=}}</ref>

==== Sensor Placement ====
A store may have a limited amount of cameras to allocate in its interior to monitor its environment, since the "world " will be partially observable, using POMDP can help reconstruct intruder position or in the contrary facilitate "stealthy" movement.

==== Games ====
Some games (like poker) have hidden states, with POMDPs we can potentially compute a best response to a fixed opponent policy. Although solving the full game is a Partially Observable Stochastic Game (POSG) which is harder to solve than POMDP and is beyond the scope of this page.

=== Conclusion ===
Probability theory is a powerful tool for modelling action under uncertainty, thanks to the markov assumption many algorithms have become easy to implement for this purpose. POMDPs are one of the broader algorithms in this category as they take structure from highly constrained algorithms such as MDPs and relax assumptions of observability to allow for more real-world problem solving applications.

== Annotated Bibliography ==
[1] Hansen, Eric A, Daniel S Bernstein, and Shlomo Zilberstein. “Dynamic Programming for Partially Observable Stochastic Games,” n.d., 6.

[2]G. Hollinger, S. Singh, J. Djugash, and A. Kehagias, “Efficient Multi-robot Search for a Moving Target,” The International Journal of Robotics Research, vol. 28, no. 2, pp. 201–219, Feb. 2009, doi: 10.1177/0278364908099853.

== 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.

Course:CPSC522

2020-03-02T20:58:21Z

TommasoDAmico:

{{Infobox_New_Course

|title=CPSC 522 Wiki

|picture=Image:wiki.png

|subject code=CPSC

|course number=522

|instructor=David Poole

|email=poole@cs.ubc.ca

|office= 109
|office hours= after class every day
|classroom= DMP 101

}}

[[Category:CPSC522]]
Welcome to [http://www.cs.ubc.ca/~poole/cs522/2019 CPSC 522] Wiki. This is where the participants are writing the textbook. See
http://www.cs.ubc.ca/~poole/cs522/2020/ for the main web page for the course.
==The 2020 Rules==
* These rules are editable, so you can change the rules.
* [[Course:CPSC522/StudentPresentations2020|2020 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 2 students per day.
* [[Course:CPSC522/January2020|January and February Assignment]]<nowiki/>s describes your assignments for January and February.
* [[Course:CPSC522/MarchApril2019|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

==Old (2018, 2019) Rules==
*[[Course:CPSC522/StudentPresentations2018|2018 Student Presentation Schedule]] is the schedule for presentations. '''Please sign up early. This is first-come first-choice.''' There is a maximum of 3 students per day.
* [[Course:CPSC522/January2018|January Assignment]] describes your assignment for January.
* [[Course:CPSC522/February2018|February Assignment]] describes your assignment for February.
* [[Course:CPSC522/MarchApril2018|March-April Assignment]] describes your 3rd assignment.
* Do not plagiarize; give references to all sources. Put quotes in quotes.
* All pages should follow the [[Course:CPSC522/Template|CPSC522 Template]]
* Give links, but make sure that the pages are readable (with sentences) without following the links.
* Link to all prerequisite pages (those the page builds on) in the appropriate place in the template. The prerequisite pages should not form a cycle.
* Link to all related pages; it should be easy for someone to determine that a page on a particular topic does not exist.
* The web pages created should all be in the [[Course:CPSC522]] hierarchy, but should not contain "Course:CPSC522" in the visible link. Hint: create a link to the page before the page exists, then you will be asked to create the page,
* If you want to abandon a page that others are relying on (e.g., you are the principal author and they are coauthors) you need to negotiate with them to make sure no one is disadvantaged.
* All pages should be in the [[Course:CPSC522/Index|Index]] and the table of contents below.

== Guidelines ==
* Keep each page as simple as possible (but not simpler); if a page starts to get complicated, consider splitting it.
* Write pages for your peers; they should all be written for incoming graduate students, and only assume background knowledge that is common among such students.
* All pages should obey the [[Course:CPSC522/Conventions|Syntax Conventions]]. If there is a design decision that you need to make that may have non-local implications, add it to the conventions.
* It should use formalism and mathematics when (and only when) the formalism make the description clearer. Use the code tags for math, e.g., <math>P(h\mid e) = \frac{P(h\land e)}{P(e)}.</math> It is worth your while to learn [https://www.latex-project.org/ Latex] if you don't already know it.
* If there is a simple case, and a more general case, give the simple case first. Making things complicated is easy; keeping them simple is difficult and we should strive for simplicity. Any complication needs to be carefully motivated.
* Use the "discussion" tab

Each Page should contain:
* A clear jargon-free description of what is going on. Keep jargon to a minimum.
* Motivating example(s) and, where appropriate, a simple pedagogical example (which may be different from the motivating examples) that is used to explain what is going on
* An argument of plausibility
* Evidence that it works
* Code and pseudo-code, where appropriate. This code should interact with other related code (e.g., [http://aipython.org AIFCA Python Distribution]) if possible. The code should be as simple as possible to implement the techniques. Consider adding exercises as to what can be improved or made more general or bullet-proof. Use a <code>code block</code> for (pseudo-)code (even multi-line code). You can also use the format in http://wiki.ubc.ca/Course:CPSC_320/Midterm_2_Reference_Sheet#Pseudocode (try both and see which better suits your needs).

==Foundations==
Please add your page here and in the [[Course:CPSC522/Index|Index]].

* [[Course:CPSC522/MyTest|My Test]]
===General===
* [[Course:CPSC522/AGI|Artificial General Intelligence]] (2018)
* [[Course:CPSC522/Swarm_Intelligence|Swarm Intelligence]] (2018)

===Control===
* [[Course:CPSC522/Control Theory|Control Theory]] (2016)
* [[Course:CPSC522/Hierarchical Control|Hierarchical Control]] (2016)

===Probability and Graphical Models===
* [[Course:CPSC522/Probability|Probability]] (2016)
* [[Course:CPSC522/Graphical Models|Graphical Models]] (2016)
* [[Course:CPSC522/Bayesian Networks|Bayesian Networks]] (2016)
* [[Course:CPSC522/Markov_Networks|Markov Networks]] (2016)
* [[Course:CPSC522/WeightedModelCounting|Weighted Model Counting]](2019)
====Temporal Models====
* [[Course:CPSC522/Markov Chains|Markov Chains]] (2018)
* [[Course:CPSC522/Hidden_Markov_Models|Hidden Markov Models]] (2016)
* [[Course:CPSC522/Kalman_filter|Kalman filter]] (2018)
* [[Course:CPSC522/Dynamic Bayesian Networks|Dynamic Bayesian Networks]] (2018)
====Inference====
* [[Course:CPSC522/Variable Elimination|Variable Elimination]] (2016)
* [[Course:CPSC522/MCMC|Markov Chain Monte Carlo]] (2016)
* [[Course:CPSC522/Particle Filtering|Particle Filtering]] (2016)
* [[Course:CPSC522/Treatment of Missing Data|Treatment of Missing Data]] (2019)
* [[Course:CPSC522/Bayesian Coresets|Bayesian Coresets]] (2019)

====Causality====
* [[Course:CPSC522/Causality|Causality]] (2016)
====Representations of Conditional Probability====
* [[Course:CPSC522/Neural Network|Neural Network]] (2016)
* [[Course:CPSC522/Recurrent Neural Networks|Recurrent Neural Networks]] (2018)
* [[Course:CPSC522/Decision_Trees|Decision Trees]] (2018)
====Learning====
* [[Course:CPSC522/Learning Probabilistic Models with Complete Data|Learning Probabilistic Models with Complete Data]] (2018)
* [[Course:CPSC522/Support_Vector_Machines|Support Vector Machines]] (2018)
* [[Course:CPSC522/Ensemble Learning|Ensemble Learning]] (2018)
* J1 [[Course:CPSC522/Principal_Component_Analysis|Principal Component Analysis (PCA)]] (2020)
* J2 [[Course:CPSC 522/Self-Organizing Maps|Self-Organizing Maps]] (2020)
===NLP===
* [[Course:CPSC522/Natural Language Processing | Natural Language Processing]] (2018)
* [[Course:CPSC522/PCFG|Probabilistic Context Free Grammars]] (2018)

===Utility and Preferences===

* [[Course:CPSC522/Bounded Rationality|Bounded Rationality]] (2018)
* [[Course:CPSC522/Elicitation of Factored Utilities|Elicitation of Factored Utilities]] (2019)

===Acting Under Uncertainty===
* [[Course:CPSC522/Decision Networks|Decision Networks]] (2016)
* [[Course:CPSC522/Markov Decision Process|Markov Decision Process]] (2016)
* F0 [[Course:CPSC522/Partially Observable Markov Decision Processes|Partially Observable Markov Decision Processes]]
* [[Course:CPSC522/Reinforcement Learning|Reinforcement Learning]] (2016)
* [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning with Function Approximation]] (2016)
* [[Course:CPSC522/Game Theory|Game Theory]] (2016)
* [[Course:CPSC522/Multi-Agent Systems|Multi-Agent Systems]] (2018)
* [[Course:CPSC522/Stochastic Optimization|Stochastic Optimization]] (2018)
* [[Course:CPSC522/Value of Information and Control|Value of Information]] (2019)

===Logic===
* [[Course:CPSC522/Abduction|Abduction]] (2018)
* [[Course:CPSC522/Knowledge Compilation|Knowledge Compilation]] (2016)
* [[Course:CPSC522/Predicate Calculus|Predicate Calculus]] (2016)
* [[Course:CPSC522/Markov Logic|Markov Logic]] (2018)
* [[Course:CPSC522/Higher Order Logic|Higher Order Logic]] (2018)
* [[Course:CPSC522/Ontology|Ontology]] (2019)

==Existing Combinations (2016)==
* [[Course:CPSC522/Recommendation System using Matrix Factorization|Recommendation System using Matrix Factorization]]
* [[Course:CPSC522/Latent Dirichlet Allocation|Latent Dirichlet Allocation]]
* [[Course:CPSC522/Deep Neural Network|Deep Neural Network and Game of Go]]
* [[Course:CPSC522/Problog|Problog]]
* [[Course:CPSC522/Maximum Entropy Markov Models|Maximum Entropy Markov Models]]
* [[Course:CPSC522/Future Directions for Semantic Systems|Ontology Search Engine]]
* [[Course:CPSC522/Convolutional Neural Networks|Convolutional Neural Networks]]
* [[Course:CPSC522/Learning Markov Logic Network Structure|Learning Markov Logic Network Structure]]
* [[Course:CPSC522/Decision Support System using Interactive Preference Elicitation|Decision Support System using Interactive Preference Elicitation]]
* [[Course:CPSC522/Predicting Affect of User's Interaction with an Intelligent Tutoring System|Predicting Affect of User's Interaction with an Intelligent Tutoring System]]
* [[Course:CPSC522/Record Linkage and identity uncertainty|Record Linkage and identity uncertainty]]
* [[Course:CPSC522/Robot Scientist|Robot Scientist]]
* [[Course:CPSC522/Density-Based Unsupervised Learning|Density-Based Unsupervised Learning]]
* [[Course:CPSC522/Predicting Human Behavior in Normal-Form Games|Predicting Human Behavior in Normal-Form Games]]
* [[Course:CPSC522/Identity Uncertainty|Identity Uncertainty]]
* [[Course:CPSC522/Generative Adversarial Networks|Generative Adversarial Networks]]

* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
*[[Course:CPSC522/User-Adaptive Information Visualization|User-Adaptive Information Visualization]]

==Existing Combinations (2020)==
* J0 [[Course:CPSC522/Variational Inference|Variational Inference]]
* J3 [[Course:CPSC522/Monte Carlo Localization |Pedestrian localization for Indoor Environments]] (2020)
* J4 [[Course:CPSC522/Automation of hypothesis generation and testing in science|Automation of hypothesis generation and testing in science]] (2020)
* J5 [[Course:CPSC522/Deep Q Network |Prioritized Experience Replay]] (2020)
* [[Course:CPSC522/Combining_Collaborative_Filtering_with_Personal_Agents_for_Better_Recommendations | Hybrid Recommendation Systems]] (2020)
* [[On-line Pattern Analysis by Evolving Self-organizing Maps]](2020)

==Existing Combinations (2018)==
===Neural Networks===
* [[Course:CPSC522/Financial Forecasting using LSTM Networks |Financial Forecasting using LSTM Networks]] (2018)
* [[Course:CPSC522/Character Level Language Models using LSTM|Character Level Language Models using LSTM]] (2018)
* [[Course:CPSC522/TextSummarizationUsingMachineLearning |Text Summarization using Machine Learning]] (2018)
* [[Course:CPSC522/Password_cracking_using_PCFGs_and_Neural_Networks|Password Cracking using Probabilistic Context Free Grammars and Neural Networks]] (2018)
* [[CNNs in Image Segmentation]](2018)
* [[Course:CPSC522/Image_Classification_With_Convolutional_Neural_Networks|Image Classification With Convolutional Neural Networks]] (2018)
* [[Image Colourization using Deep Learning]](2018)
* [[Course:CPSC522/StackedGAN|Stacked Generative Adversarial Networks]] (2018)

===Reinforcement Learning===
* [[Course:CPSC522/Deep_Q-Learning|Deep Q-Learning]] (2018)
* [[Course:CPSC522/Deep_Reinforcement_Learning|Deep Reinforcement Learning]] (2018)
* [[Course:CPSC522/Self_Improving_Machines|Self-Improving Machines]] (2018)
* [[Course:CPSC522/Adaptive_Network_Routing_using_ACO|Adaptive Network Routing using Ant Colony Optimization]] (2018)
===Decision-theoretic Planning===
* [[Course:CPSC522/Action_Selection_for_MDPs|Action Selection for MDPs]] (2018)
* [[Course:CPSC522/Rao_Blackwellized_Particle_Filtering|Rao-Blackwellized Particle Filtering]](2018)
===Relational Reasoning===
* [[Course:CPSC522/Transfer_Learning_with_Markov_Logic|Transfer Learning with Markov Logic]] (2018)
* [[Course:CPSC522/Cognitive_Robotics|Cognitive Robotics]] (2018)
===Applications===
* [[Course:CPSC522/Affect Prediction using Eye Gaze|Affect Prediction using Eye Gaze]] (2018)
* [[Course:CPSC522/Conflict-Driven Clause Learning for the Boolean Satisfiability Problem|Conflict-Driven Clause Learning for the Boolean Satisfiability Problem]] (2018)

==Existing Combinations (2019)==
* [[Course:CPSC522/Ontology Extraction|Ontology Extraction]]
* [[Course:CPSC522/Restricted Boltzmann Machines for Collaborative Filtering|Restricted Boltzmann Machines for Collaborative Filtering]]
* [[Course:CPSC522/Minimax Regret Preference Elicitation for Risky Prospects|Minimax Regret Preference Elicitation for Risky Prospects]]
* [[Course:CPSC522/Sequential Monte Carlo samplers|Sequential Monte Carlo samplers]]
* [[Course:CPSC522/FastSLAM|FastSLAM]]
* [[Course:CPSC522/SMC for PGMs|Sequential Monte Carlo for Probabilistic Graphical Models]]

==Future combinations (2016)==
* [[Course:CPSC522/Sentiment Analysis|Sentiment Analysis: Movie Reviews]]
* [[Course:CPSC522/Collaborative Filtering|Collaborative Filtering]]
* [[Course:CPSC522/List Recommendation|List Recommendation]]
* [[Course:CPSC522/Inactive Cookie Mapping via Trail Matching|Inactive Cookie Mapping via Trail Matching]]
* [[Course:CPSC522/Improve recommendation system by integration|Improve Recommendation System by Integration]]
* [[Course:CPSC522/Identity Uncertainty in a restaurant data-set|Identity Uncertainty in a restaurant data-set]]
* [[Course:CPSC522/Regularization_for_Neural_Networks|Regularization for Neural Networks]]
* [[Course:CPSC522/Spam Detection|Spam Detection]]
* [[Course:CPSC522/Titanic: Machine Learning from Disaster|Titanic: Machine Learning from Disaster]]
* [[Course:CPSC522/Automatic Classification of Morphological Heart Arrhythmia | Automatic Classification of Morphological Heart Arrhythmia]]
* [[Course:CPSC522/Linking Sentences in Asynchronous Conversations|Linking Sentences in Asynchronous Conversations]]
* [[Course:CPSC522/Generic Aspect-based Aggregation of Sentiments|Generic Aspect-based Aggregation of Sentiments]]
* [[Course:CPSC522/Graph Based keyword extraction|Graph Based Key-corporation Extraction]]
* [[Course:CPSC522/Improving the accuracy of Affect Prediction in an Intelligent Tutoring System|Improving the accuracy of Affect Prediction in an Intelligent Tutoring System]]
* [[Course:CPSC522/Improving Human Behavior Prediction in Simultaneous-Move Games|Improving Human Behavior Prediction in Simultaneous-Move Games]]
* [[Course:CPSC522/The Automation of Disease Diagnosis|The Automation of Disease Diagnosis]]
* [[Course:CPSC522/Analyzing online dating trends with Weka|Analyzing online dating trends with Weka]]

==Future combinations (2018)==
* [[Course:CPSC522/Artificial Intelligence and Economic Theory|Artificial Intelligence and Economic Theory]]
* [[Course:CPSC522/Weak Semantic Map|Weak Semantic Map: Simplified Chinese]]
* [[Course:CPSC522/Network Agent|Datacenter Traffic as Reinforcement Learning Problem]]
* [[Course:CPSC522/Baseilne_of_RSI|A Theoretical Baseline of Recursive Self-improvement]]
* [[Course:CPSC522/Text_Summarization_for_busy_people!| Text summarization for busy people!!]]
* [[Course:CPSC522/An_evaluation_on_selecting_and_applying_Recommendation_Methods | An evaluation on selecting and applying Recommendation Methods]]
* [[Course:CPSC522/Learning User Preferences of Motion Control | Learning User Preferences of Motion Control]]
* [[Course:CPSC522/Experiments_with_Reinforcement_Learning| Experiments with Reinforcement Learning]]
* [[Course:CPSC522/A_Comparison_of_LDA_and_NMF_for_Topic_Modeling_on_Literary_Themes| A Comparison of LDA and NMF for Topic Modeling on Literary Themes]]
* [[Course:CPSC522/Analysis of hierarchical prior for Language modeling | Analysis of hierarchical prior for Language modeling]]
* [[Better_caching_using_reinforcement_learning|Better Caching using reinforcement learning]]
* [[Course:CPSC522/Evaluation_of_ACO|Evaluating Ant Colony Optimization in a simulation]]
* [[Course:CPSC522/SLAM_And_Sensor_Quality|SLAM and Sensor Quality]]
* [[Text generation with LSTM and Markov Chain]]
* [[Course:CPSC522/Topology_and_Embedding_Multi-relational_Data|Topology and Embedding Multi-relational Data]]

== Future combinations (2019) ==
* [[Course:CPSC522/Reinforcement Learning with Linear Model of Reward Corruption|Reinforcement Learning with Linear Model of Reward Corruption]]
*
* [[Course:CPSC522/Adverserial Belief Propagation|Adversarial Belief Propagation]]
*
* [[Course:CPSC522/Using Subset Information with Matrix Factorization|Using Subset Information with Matrix Factorization]]
*
* [[Course:CPSC522/Learning Attention via Active Inference|Learning Attention via Active Inference]]
* [[Course:CPSC522/Regularization as an Alternative to Negative Sampling in KGs|Regularization as an Alternative to Negative Sampling in KGs]]
==Suggested Unclaimed Pages==
Here are some possible topics for pages. This list is not meant to limit your imagination. Some of them might be better split into multiple pages. There are many other possible topics.

When claimed, these pages should be moved from this section to the table of contents above and to the [[Course:CPSC522/Index|Index]] of existing pages. To claim a page you have to actually create it and edit it (and have your name on the page, so everyone can see who has claimed it).

* [[Course:CPSC522/Probability general semantics|Probability - general semantics]] with infinitely many variables and/or variables with infinite domains
* [[Course:CPSC522/Representations of Conditional Distributions|Representations of Conditional Distributions]]
* [[Course:CPSC522/Recursive Conditioning|Recursive Conditioning]]
* [[Course:CPSC522/Parity Methods|Parity Methods for Probabilistic Inference]]
* [[Course:CPSC522/Matrix Factorization|Matrix Factorization]]
* [[Course:CPSC522/Utility|Utility]]
* [[Course:CPSC522/Multi-Attribute Utility|Multi-Attribute Utility]]
* [[Course:CPSC522/Preference Elicitation|Preference Elicitation]]
* [[Course:CPSC522/Mechanism Design|Mechanism Design]]
* [[Course:CPSC522/Logic Programming|Logic Programming]]
* [[Course:CPSC522/Negation as Failure|Negation as Failure]]
* [[Course:CPSC522/Equality-Identity|Equality/Identity]]
* [[Course:CPSC522/Inductive Logic Programming|Inductive Logic Programming]]
* [[Course:CPSC522/Ontologies|Ontologies]]
* [[Course:CPSC522/Continual Learning|Continual Learning]]

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-02T02:42:48Z

TommasoDAmico: First Draft Complete

== Partially Observable Markov Decision Processes (POMDPs) ==
A Partially Observable Markov Decision Processes (POMDs) is a mathematical model for acting under uncertainty. It expands from the Markov Decision Process (MDP) by relaxing the constraint of having a fully observable state space. In this paper we will evaluate the underlying mathematical model and explore the potential of POMDPs for belief MDP.

Principal Author: Tommaso D'Amico

Collaborators:

== Abstract ==
POMDPs are a type of Decision Network that expands from Markov Decision Processes by not requiring all states to be observable by the agent. POMDPs still maintain the same system dynamics of an MDP although the acting agent cannot always observe its current state but rather it needs to maintain a probability distribution over the set of possible states it may be in based on its observations and the underlying MPD.

=== Builds on ===
POMDPs is a mathematical model expanding from the concepts of [https://wiki.ubc.ca/Course:CPSC522/Decision_Networks Decision networks], specifically generalizing from the [[Course:CPSC522/Markov Decision Processes|Markov Decision Process]] algorithm for acting under uncertainty.

=== Related Pages ===
POMDPs are widely implemented in applications that interact with the real world, some examples are particle filtering techniques such as MC-POMDPs, an extension of [https://wiki.ubc.ca/Course:CPSC522/MCMC Markov Chains Monte Carlo] for POMDPs, [[Course:CPSC522/Reinforcement Learning with Function approximation|Reinforcement Learning]] and game logic with Partially Observable Stochastic Games (POSG)<ref>Hansen, Eric A, Daniel S Bernstein, and Shlomo Zilberstein. “Dynamic Programming for Partially Observable Stochastic Games,” n.d., 6.</ref>.

POMDPs are also closely related to [https://en.wikipedia.org/wiki/Hidden_Markov_model Hidden Markov Models] and [https://en.wikipedia.org/wiki/Markov_chain Markov Chains].

== Content ==

=== Introduction ===
[[File:State Machine illustration.jpg|thumb|POMDP Example with two states s1,s2 and two actions a1 and a2]]
Partially Observable Markov Decision Processes (POMDPs) are a type of Markov Process closely related to Markov Decision Processes (MDP) as:
* there exist a finite number of discrete states
* the next state is only determined by the current state and the current action taken by the agent
* there exists a probabilistic transition between states and controllable actions in each state
The way a POMDP differs from an MDP is that the agent is unsure of which state it is in as it has only partial observability of the environment states. It instead needs to develop a probability distribution over the set of states it believes to be in and condition its observations and the underlying MDP structure. A comparison can be drawn for clarity to the relationship of Markov Chains with Hidden Markov Models, as the latter too is an extension of the prior with reduced observability. In fact a helpful illustration of the difference among these models can be seen in the chart below:
{|
|+'''Helpful Chart for Markov Model Segmentation'''
| colspan="2" rowspan="2" |
| colspan="2" rowspan="1" |'''Does the agent have control over state transition?'''
|-
|no
|yes
|-
| colspan="1" rowspan="2" |'''Are the states fully observable?'''
|yes
|Markov Chain
|MDP
|-
|no
|HMM
|POMDPs
|}

==== POMDP versus MPD ====
MPD is more tractable to solve and is relatively easy to specify although it assumes perfect knowledge of the states which is often unlikely for many use cases.

POMDP on the other hand treats all sources of uncertainty uniformly and allows for information gathering actions, although it is hugely intractable to solve optimally.

=== Formal Definition ===
Formally a POMDP working in discrete-time models the relationship between an agent and its environment. This is commonly done with a 7-tuple <math>(S,A,T,R,\Omega, O,\gamma)</math>where:
* <math>S</math>is a set of all states
* <math>A
</math>is a set of all actions
* <math>T
</math>is a set of conditional transition probabilities between states
* <math>R:S \times A\rightarrow \R
</math>is the reward function
* <math>\Omega</math>is the set of observations
* <math>O</math>is the set of conditional observation probabilities
* <math>\gamma \in [0,1]
</math>is the discount factor
At each time step the environment is in state <math>s \in S
</math>. The agent takes action <math>a \in A
</math>, which causes the environment to transition to <math>s'
</math>with probability given by <math>T(s' | s,a).
</math>at the same time the agent receives an observation <math>o \in \Omega
</math>which is dependent on the new environment state <math>s'

</math>and the action <math>a
</math>just done by the agent, this is described by the probability distribution of <math>O(o|s',a)
</math>. This state and action is then used to develop a reward <math>r
</math>equal to <math>R(s,a)
</math>. This process then repeats for the next time step until the agent completes its task or to infinity. The goal is for the agent to maximize its expected future discounted reward: <math>E[ \sum_{t=0}^\inf\gamma^tr_t ]
</math>, where <math>r_t
</math>is the reward earned at time <math>t

</math>. <math>\gamma
</math>is the discount factor that determines how much immediate rewards are favoured over distant rewards. When <math>\gamma = 0

</math>the agent only cares about which action will yield the largest expected immediate reward, while if <math>\gamma = 1

</math>the agent cares about maximizing the expected sum of future rewards.

==== Belief Update ====
after executing one time step an agent needs to update its belief of the state of the environment it is in. Since we assume a ''Markovian'' state space, all we need to describe to execute this step is our prior state belief <math>b</math>, the last action <math>a</math>taken by the agent and the last observation made <math>o</math>.

The update step can be denoted as <math>b' = \tau(b,a,o)</math>.

After reaching state <math>s'</math>, the agent observes <math>o \in \Omega
</math>with probability <math>O(o|s',a)
</math>as described in the prior section.

If we then let <math>b</math> be a probability distribution over the state space <math>S</math>then <math>b(s)</math>denotes the probability that the environment is in state <math>s</math>. Given <math>b(s)</math>, then after taking an action <math>a</math>and an observation <math>o</math>,

<math>b'(s') = \eta O(o|s',a) \sum_{s \in S} T(s' |s,a)b(s)</math>

where <math>\eta = 1 / Pr(o|b,a)</math> is used as a normalising constant with

<math>Pr(o|b,a) = \sum_{s' \in S} O(o|s',a) \sum_{s \in S} T(s' | s,a)b(s)</math>

==== Interpretation of Definition ====
From the above definition the agent does not directly observe its environment. It instead has to make decisions about the true environment state under uncertainty. However, by interacting with the environment and receiving observations the agent is able to update its belief of the true state by updating the probability distribution of the current state. Through this property of the algorithm the extrapolated optimal behaviour may often include actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in future time steps.

If we compare the formal definition of the POMDP described above with that of MDP we would have a very similar structure with the exception that the MDP algorithm would not include the conditional observation probabilities set <math>O</math>as it is always certain of the observed true state.

=== Belief MDP ===
A Markovian belief state allows a POMDP to be formulated as an Markov Decision Process where every belief is a state. The resulting belief MDP will thus be defined on a continuous state space even though the the originating POMDP has a finite number of states. This is because there are infinite number of probability distributions over the state set.

The belief MDP is formally described as a tuple <math>(B,A,\tau ,r ,\gamma )</math>where

<math>B</math>is the set of belief states over the POMDP states

<math>A</math>is the same finite set of actions as in the POMDP algorithm

<math>\tau</math>is the belief state transition function

<math>r: B \times A \rightarrow \R</math>is the reward function on belief states

<math>\gamma</math>is the discount factor equal to the one in the original POMDP

from these values <math>\tau
</math>and <math>r</math>are derived from the oroginal POMDP via

<math>\tau (b,a,b') = \sum_{o \in \Omega} Pr(b'|b,a,o)Pr(o|a,b)</math>

where <math>Pr(o|a,b)</math> is the value derived in the previous section and

<math>Pr(b'|b,a,o) = \begin{cases} 1, & \text{if the belief update with arguments } b,a,o \text{ returns } b' \\ 0, & \text{otherwise} \end{cases}

</math>

and the reward function is the expected reward from the POMDP reward function over the belief distribution as follows <math>r(b,a) = \sum_{s \in S} b(s)R(s,a)
</math>

By going through these steps the belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP.

This means we were able to take a partially observable discrete space system and convert it to a continuous space fully observable belief system.

=== Applications of POMDP ===

==== Pursuit-Evasion ====
Imagine a fleet of robots in a constrained environment, assign one robot to pursuit the others. The pursuer's state is known, but the evader's state is only partially observed. POMDP can be applied by the evaders in a multi-agent search fashion to observe the environment and build a belief of the pursuer's location.<ref>{{Cite journal|last=Hollinger, Singh|first=|date=|title=Efficient Multi-robot Search for a Moving Target|url=https://journals.sagepub.com/doi/10.1177/0278364908099853|journal=The International Journal of Robotics Research|volume=|pages=|via=}}</ref>

==== Sensor Placement ====
A store may have a limited amount of cameras to allocate in its interior to monitor its environment, since the "world " will be partially observable, using POMDP can help reconstruct intruder position or in the contrary facilitate "stealthy" movement.

Games

Some games (like poker) have hidden states, with POMDPs we can potentially compute a best response to a fixed opponent policy. Although solving the full game is a Partially Observable Stochastic Game (POSG) which is harder to solve than POMDP and is beyond the scope of this page.

=== Conclusion ===
Probability theory is a powerful tool for modelling action under uncertainty, thanks to the markov assumption many algorithms have become easy to implement for this purpose. POMDPs are one of the broader algorithms in this category as they take structure from highly constrained algorithms such as MDPs and relax assumptions of observability to allow for more real-world problem solving applications.

== Annotated Bibliography ==
[1] Hansen, Eric A, Daniel S Bernstein, and Shlomo Zilberstein. “Dynamic Programming for Partially Observable Stochastic Games,” n.d., 6.

[2]G. Hollinger, S. Singh, J. Djugash, and A. Kehagias, “Efficient Multi-robot Search for a Moving Target,” The International Journal of Robotics Research, vol. 28, no. 2, pp. 201–219, Feb. 2009, doi: 10.1177/0278364908099853.

== 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.

File:State Machine illustration.jpg

2020-03-02T01:52:21Z

TommasoDAmico: User created page with UploadWizard

=={{int:filedesc}}==
{{Information
|description={{en|1=State Machine Illustration with 2 States and 2 actions}}
|date=2020-03-01
|source={{own}}
|author=[[User:TommasoDAmico|Tommaso D'Amico]]
|permission=
|other versions=
}}

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

[[Category:CPSC522]]

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-01T23:25:58Z

TommasoDAmico: added formal definition

Course:CPSC522/Partially Observable Markov Decision Processes

2020-03-01T22:21:12Z

TommasoDAmico: Setup page for POMDPs

Course:CPSC522/Monte Carlo Localization

2020-02-10T21:29:44Z

TommasoDAmico:

== Monte Carlo Pedestrian Localization for Indoor Environments ==
This page gives an overview of the Monte Carlo Localization method (MCL)<ref name=":0" /> and demonstrates an extension of the technique to enable for pedestrian tracking within a building environment.<ref name=":1" />

Principal Author: Tommaso D'Amico

Collaborators: -

Papers Discussed:

- Fox, Dieter, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun. “Monte Carlo Localization: Efﬁcient Position Estimation for Mobile Robots,” In ''Proc''.''of the IEEE International Conference on Robotics & Automation (ICRA)''. 1999, 7.

- Woodman, Oliver, and Robert Harle. “Pedestrian Localisation for Indoor Environments.” In ''Proceedings of the 10th International Conference on Ubiquitous Computing - UbiComp ’08'', 114. Seoul, Korea: ACM Press, 2008. <nowiki>https://doi.org/10.1145/1409635.1409651</nowiki>.

== Abstract ==
This page gives an overview of the Monte Carlo Localization method (MCL)<ref name=":0">Fox, Dieter, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun. “Monte Carlo Localization: Efﬁcient Position Estimation for Mobile Robots,” In ''Proc''.''of the IEEE International Conference on Robotics & Automation (ICRA)''. 1999, 7.</ref> and demonstrates an extension of the technique to enable for pedestrian tracking within a building environment<ref name=":1">Woodman, Oliver, and Robert Harle. “Pedestrian Localisation for Indoor Environments.” In ''Proceedings of the 10th International Conference on Ubiquitous Computing - UbiComp ’08'', 114. Seoul, Korea: ACM Press, 2008. <nowiki>https://doi.org/10.1145/1409635.1409651</nowiki>.</ref>. MCL is analyzed as a technique for pedestrian localization as it allows for global localization with multi modal probability distributions over continuous space and is shown to be robust to highly noisy sensors. The Pedestrian Localization paper demonstrates a technique to extend MCL to a 2.5D map and illustrates the benefits of it for reducing uncertainty.

=== Builds on ===
The Monte Carlo Localization method is an algorithm that utilizes [[Course:CPSC522/Particle Filtering|particle filtering]] as a means of localization. It builds on the idea of using [[Course:CPSC522/Probability|Bayesian probability]] with [[Course:CPSC522/Markov Chains|Markov Chains]] to develop a [[Course:CPSC522/Probability|probability distribution]] of the likely states of a robot to aid it in its localization.

For the adaptation of MCL to pedestrians in indoors environments the [https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence Kullback-Leibler divergence (KLD)] sampling algorithm is used to dynamically adapt the number of particles sampled.

=== Related Pages ===
a related combination of Monte Carlo Method with Markov Chains is the [[Course:CPSC522/MCMC|MCMC algorithm]].

== Content ==

=== Monte Carlo Localization (MCL) ===
The goal of Monte Carlo Localization is to allow a robot to localize itself in an environment given only an odometry system, a sensor to perceive its surroundings and a 2D map of its navigable environment<ref name=":0" />. In this page we will also explore the use of MCL without the aid of a sensor to perceive the surroundings<ref name=":1" /> and how it is still capable of providing accurate estimates using different aids and assumptions.

==== Global Localization and Position Tracking ====
Localization for robotics is often broken down in two categories: Global localization and position tracking<ref name=":0" />. In position tracking the robot knows its initial position and only needs to accommodate for small errors or drift in the odometry system as it moves. Global Localization is a bit more complex as it looks at identifying the robots' position within its global environment given no initial state.<ref name=":0" /> This is also referred to as the [https://en.wikipedia.org/wiki/Kidnapped_robot_problem hijacked robot problem]. Since the robot needs to localize itself from scratch, this tends to be a very computationally heavy process and is often omitted by most localization algorithms.<ref name=":0" />

==== MCL Algorithm ====
[[File:Sca80a0 Animation of Monte Carlo Localization using laser range finders.gif|thumb|Animation showing the operation of the Monte Carlo Localization for a robot using laser range finders]]
Monte Carlo Localization is generically known as a particle filter. The key idea of the method is to represent the posterior belief <math>Bel(l)</math>by a set of <math>N</math> weighted, random samples or ''particles'' <math>S = {(s_i | i = 1...N)}</math><ref name=":0" />. A sample set constitutes a discrete approximation of a probability distribution<ref name=":0" />. In MCL the samples are of type <math>\langle\langle x,y,\theta\rangle,p\rangle</math>where <math>x,y,\theta
</math>represent the coordinates on the 2D map and the robot orientation, while <math>p \ge 0</math> represents a discrete probability of the likelihood of the particle<ref name=":0" />.

MCL operates in two steps, the robot ''motion step'' and the ''sensor reading step''.

''When the robot moves'' MCL generates <math>N</math>new samples that approximate the robot's position after the motion command. Each sample is generated by randomly drawing a sample from the previously computed sample set with likelihood determined by their p-values<ref name=":0" />. Let <math>l'</math> denote the position of this sample. The new sample’s <math>l</math> is then generated by generating a single, random sample from <math>P(l|l',a)</math>, using the action <math>a
</math> as observed. The p-value of the new sample is <math>N^{-1}</math>.<ref name=":0" />

''Sensor readings'' are incorporated by re-weighting the sample set, in a way that implements Bayes rule in Markov localization. More specifically, let <math>\langle l,p \rangle
</math>be a sample<ref name=":0" />. Then <math>p \longleftarrow a P(s | l)
</math> where <math>s
</math> is the sensor measurement, and <math>a
</math> is a normalization constant that enforces the sum of all p-values to 1<ref name=":0" />. The incorporation of sensor readings is typically performed in two phases, one in which <math>p</math> is multiplied by <math>P(s | l)

</math>, and one in which the various p-values are normalized.<ref name=":0" />

In practice the introduction of a small number of uniformly distributed random samples at each step is recommended to enable re-localization in the rare event that the robot looses track of its position.<ref name=":0" />

==== Properties of MCL ====
The main property that makes MCL such a powerful algorithm is that it can universally approximate arbitrary probability distributions. The variance of the importance sampler converges to zero at a rate of <math>1/\sqrt{N}</math>(under MCL conditions). This creates a clear trade-off of accuracy and computational load<ref name=":0" />. However, the true advantage lies in the way MCL places computational resources on regions with high likelihood, where things really matter<ref name=":0" /> also known as adaptive sampling. More about this is shown in the second paper description below.

Given there is no [https://en.wikipedia.org/wiki/Discretization discretization] of the space or the data, MCL is able to estimate the state of the robot to any numerical accuracy given sampling size.<ref name=":0" />

MCL is an online algorithm, meaning that it leads itself nicely to an any-time implementation. This means that the algorithm is able to provide an answer at any time, however the quality of the solution increases with time.<ref name=":0" />

=== Pedestrian Localization for Indoor Environments ===
The pedestrian localization problem is the second paper of this page, it builds upon the MCL algorithm and adapts it to the localization of pedestrians in an indoor environment. In particular this paper looks at how a foot-mounted inertial unit, a detailed building model, and a particle filter can be combined to provide absolute positioning, despite the presence of drift in the inertial unit and without knowledge of the user’s initial location<ref name=":1" />.

There are several differences between robot and pedestrian localisation as presented in the paper. Firstly, the robots used in existing literature have been unable to climb stairs. As a result, a 2-dimensional map of the environment has been sufficient. Secondly, the movement of a robot can be actively controlled. This is clearly not possible in a pedestrian localisation system. Thirdly, robot localisation is typically solved knowing both the relative movement of the robot and measurements obtained from a laser range finder. In contrast, only relative movement information is used (in the form of step events) to solve the pedestrian localisation problem.

==== 2.5D Mapping ====
[[File:2.5D map lecture room.png|thumb|315x315px|Illustration of a 2.5D map. It illustrates the way stairs and walls are mapped in the environment.]]
There are many obstacles that limit the possible movement of a pedestrian within a building. In particular walls are impassable obstacles. In order to enforce such constraints it is necessary to have a computer-readable plan of the building. Since it is reasonable to assume that a pedestrian’s foot is constrained to lie on the floor during the stance phase of the gait cycle, a 2.5-dimensional description of the building (in which each object has a vertical position but no depth) is sufficient<ref name=":1" />. Hence a map is defined to be a collection of planar floor polygons.Each floor polygon corresponds to a surface in the building on which a pedestrian’s foot may be grounded<ref name=":1" />. Each edge of a floor polygon is either an impassable wall or a connection to the edge of another polygon. Connected edges must coexist in the (x,y) plane, however they may be separated in the vertical direction to allow the representation of stairs<ref name=":1" />.

==== Tracking using a foot mounted IMU ====
Although we're dealing with tracking people, the MCL is usually applied to robots, where mobile devices typically use inertial sensors, laser range-finders and computer vision to provide accurate localisation without the requirement of fixed infrastructure<ref name=":1" />. Applying the same systems to people is, however, fraught with difficulties; laser range-finders and cameras are impractical, we lose the ability to control the subject to maximize our chances of precise localisation, and the techniques are usually developed with a single floor in mind<ref name=":1" />.

One type of sensor which does seem applicable to people tracking is [https://en.wikipedia.org/wiki/Inertial_measurement_unit inertial measurement units (IMUs)]. An IMU contains three orthogonal rate-gyroscopes and accelerometers, which report angular velocity and acceleration respectively. In principle, it is possible to track the orientation of the IMU by integrating the angular velocity signals. This can then be used to resolve the acceleration samples into the global frame of reference, from which acceleration due to gravity is subtracted. The remaining acceleration can then be integrated twice to track the position of the IMU relative to a known starting point and heading<ref>Titterton, D. H., and J. L. Weston. ''Strapdown Inertial Navigation Technology''. 2nd ed. IEE Radar, Sonar, Navigation, and Avionics Series 17. Stevenage: Institution of Electrical Engineers, 2004.</ref>.

For foot-mounted IMUs the cubic-in-time drift problem can be reduced by detecting when the foot is in the stationary stance phase (i.e. in contact with the ground) during each gait cycle. Zero velocity updates (ZVUs) can be applied during this phase, in which the known direction of acceleration due to gravity is used to correct tilt errors which have accumulated during the previous step. The application of such constraints replaces the cubic-in-time error growth with an error accumulation that is linear in the number of steps.<ref name=":1" />

==== Particle Propagation for pedestrian localization ====
The particle propagation for pedestrian localization closely resembles the update given by the robot motion in MCL, with an exception for determining which floor polygon to which the propagated particle is constrained. Initially it is assumed that the particle resides in the floor polygon it came from. In order for it to exit the floor polygon the step vector must intersect one of its edges in the (x,y) plane. There are three cases outlined by the authors:
# No intersection point is found. The particle must still be constrained to the same polygon.
# The first intersection C is with a wall. In this case the particle’s weight should be set to equal 0 in the correction step, enforcing the constraint that walls are impassable.
# The first intersection C is with an edge connecting to another polygon. In this case we update the current polygon to the new connected polygon.
Since a single step may span multiple connections, the intersection test is repeated between the remainder of the updated polygon. This process continues recursively until one of the first two cases applies.

==== Particle Correction for pedestrian localization ====
The correction step sets the weight <math>w_t</math>of a propagated particle. This step is used to enforce wall constraints. If a wall is intersected during the propagation step used to generate the state of the particle, then it is assigned a weight wt = 0<ref name=":1" />. If a wall is not intersected, the particle is assigned a weight based on the difference between the height change <math>\delta z

</math> of the current step and the difference in height between the start and end floor polygons. The height change according to the map is given by <math>\delta z_{poly} = Height(poly_t) - Height(poly_{t-1})
</math><ref name=":1" />.

Here we are using the change in height reported in the current step as a measurement in the Bayesian framework. Particles whose change in height over the step closely matches the change in height reported in the step event are assigned stronger weights<ref name=":1" />. This allows localisation to occur quickly when the user climbs or descends stairs.
[[File:Algorithm update particle propagation and correction for pedestrian localization.png|none|thumb|787x787px|Algorithm containing particle propagation and correction steps for pedestrian localization. Source: Woodman, Oliver, and Robert Harle. “Pedestrian Localisation for Indoor Environments.”]]

==== Re-sampling for pedestrian localization ====
The number of particles needed to represent <math>Bel(s)
</math>to a given level of accuracy depends on the complexity of the distribution, which can vary drastically over time. As a result it can be highly inefficient to use a fixed number of particles. This is particularly true for localisation problems, where the number of particles required to track an object after convergence is typically only a small fraction of the number required to adequately describe the distribution in the early stages of localisation<ref name=":1" />.

Kullback-Leibler divergence (KLD) sampling is used in this framework since likelihood-based adaptation is not well suited for problems where <math>Bel(s)
</math> can be a multi-modal distribution, as is often the case during indoor localisation due to symmetry in the environment<ref name=":1" />. The idea of KLD-sampling is to generate a number of particles at each step such that the approximation error introduced by using a sample-based representation of <math>Bel(s)
</math>remains below a specified threshold <math>\epsilon
</math>.

Since the propagation step in this framework uses control information (in the form of step events), the propagated belief is a reasonable estimate of the posterior.

=== Contributions and Comparisons ===
Taking MCL and adapting it to a pedestrian tracker requires several modifications. MCL was designed for robot localization, robots can have multiple sensors in them to provide information about the environment. Strapping a laser sensor or camera to an individual can be a difficult demand. For such reason the authors resorted in only using an IMU for localization, which makes localization much more difficult. Given humans move by walking in steps, the researchers exploited the IMU data further by making assumptions on the readings, they included ZVU to understand when a step occurred and assumed all footsteps would be in contact with the floor. This enabled the sole use of the IMU for tracking given the aforementioned assumptions and the expansion of the algorithm to a 3 dimensional environment with the 2.5D mapping trick that was show above.

From the pedestrian adaptation of MCL the main contributions to be carried forward are the concept of expanding the map to higher dimensions and the use of assumptions as constraints to reduce the number of sensors or readings needed to make the algorithm work.

The second paper introduces the use of KLD as a method for adaptive sampling, which may be relevant to general applications of MCL.

It is challenging to compare accuracy in localization for both approaches as environments and data used are very different and the nature of the algorithm in place is stochastic and can be varied in many ways. That said, reported accuracies for experiments for robotics application of MCL fall between 5-10cm with large enough sampling (~1000-10000 samples)<ref name=":0" /> while for the pedestrian application they report an accuracy of 0.5m 75% of the time and 0.73m 95% of the time<ref name=":1" />. It can be seen that the removal of observatory sensors is quite damaging to accuracy even when employing assumptions to the data being generated, although given the limited sensors and large map environment, the results can still be useful for the task at hand (Robot localization applications tend to require more accurate localization as their navigation often depends on it, human can do it themselves).

== Annotated Bibliography ==
[1] Fox, Dieter, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun. “Monte Carlo Localization: Efﬁcient Position Estimation for Mobile Robots,” In ''Proc''.''of the IEEE International Conference on Robotics & Automation (ICRA)''. 1999, 7.

[2] Woodman, Oliver, and Robert Harle. “Pedestrian Localisation for Indoor Environments.” In ''Proceedings of the 10th International Conference on Ubiquitous Computing - UbiComp ’08'', 114. Seoul, Korea: ACM Press, 2008. <nowiki>https://doi.org/10.1145/1409635.1409651</nowiki>.

[3] Titterton, D. H., and J. L. Weston. ''Strapdown Inertial Navigation Technology''. 2nd ed. IEE Radar, Sonar, Navigation, and Avionics Series 17. Stevenage: Institution of Electrical Engineers, 2004.

== 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.

Course:CPSC522/Monte Carlo Localization

2020-02-10T21:29:08Z

TommasoDAmico: Added sections and rephrased some sentences based on peer critiques

== Monte Carlo Pedestrian Localization for Indoor Environments ==
This page gives an overview of the Monte Carlo Localization method (MCL)<ref name=":0" /> and demonstrates an extension of the technique to enable for pedestrian tracking within a building environment.<ref name=":1" />

Principal Author: Tommaso D'Amico

Collaborators: -

Papers Discussed:

- Fox, Dieter, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun. “Monte Carlo Localization: Efﬁcient Position Estimation for Mobile Robots,” In ''Proc''.''of the IEEE International Conference on Robotics & Automation (ICRA)''. 1999, 7.

- Woodman, Oliver, and Robert Harle. “Pedestrian Localisation for Indoor Environments.” In ''Proceedings of the 10th International Conference on Ubiquitous Computing - UbiComp ’08'', 114. Seoul, Korea: ACM Press, 2008. <nowiki>https://doi.org/10.1145/1409635.1409651</nowiki>.

== Abstract ==
This page gives an overview of the Monte Carlo Localization method (MCL)<ref name=":0">Fox, Dieter, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun. “Monte Carlo Localization: Efﬁcient Position Estimation for Mobile Robots,” In ''Proc''.''of the IEEE International Conference on Robotics & Automation (ICRA)''. 1999, 7.</ref> and demonstrates an extension of the technique to enable for pedestrian tracking within a building environment<ref name=":1">Woodman, Oliver, and Robert Harle. “Pedestrian Localisation for Indoor Environments.” In ''Proceedings of the 10th International Conference on Ubiquitous Computing - UbiComp ’08'', 114. Seoul, Korea: ACM Press, 2008. <nowiki>https://doi.org/10.1145/1409635.1409651</nowiki>.</ref>. MCL is analyzed as a technique for pedestrian localization as it allows for global localization with multi modal probability distributions over continuous space and is shown to be robust to highly noisy sensors. The Pedestrian Localization paper demonstrates a technique to extend MCL to a 2.5D map and illustrates the benefits of it for reducing uncertainty.

=== Builds on ===
The Monte Carlo Localization method is an algorithm that utilizes [[Course:CPSC522/Particle Filtering|particle filtering]] as a means of localization. It builds on the idea of using [[Course:CPSC522/Probability|Bayesian probability]] with [[Course:CPSC522/Markov Chains|Markov Chains]] to develop a [[Course:CPSC522/Probability|probability distribution]] of the likely states of a robot to aid it in its localization.

For the adaptation of MCL to pedestrians in indoors environments the [https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence Kullback-Leibler divergence (KLD)] sampling algorithm is used to dynamically adapt the number of particles sampled.

=== '''Related Pages''' ===
a related combination of Monte Carlo Method with Markov Chains is the [[Course:CPSC522/MCMC|MCMC algorithm]].

== Content ==

=== Monte Carlo Localization (MCL) ===
The goal of Monte Carlo Localization is to allow a robot to localize itself in an environment given only an odometry system, a sensor to perceive its surroundings and a 2D map of its navigable environment<ref name=":0" />. In this page we will also explore the use of MCL without the aid of a sensor to perceive the surroundings<ref name=":1" /> and how it is still capable of providing accurate estimates using different aids and assumptions.

==== Global Localization and Position Tracking ====
Localization for robotics is often broken down in two categories: Global localization and position tracking<ref name=":0" />. In position tracking the robot knows its initial position and only needs to accommodate for small errors or drift in the odometry system as it moves. Global Localization is a bit more complex as it looks at identifying the robots' position within its global environment given no initial state.<ref name=":0" /> This is also referred to as the [https://en.wikipedia.org/wiki/Kidnapped_robot_problem hijacked robot problem]. Since the robot needs to localize itself from scratch, this tends to be a very computationally heavy process and is often omitted by most localization algorithms.<ref name=":0" />

==== '''MCL Algorithm''' ====
[[File:Sca80a0 Animation of Monte Carlo Localization using laser range finders.gif|thumb|Animation showing the operation of the Monte Carlo Localization for a robot using laser range finders]]
Monte Carlo Localization is generically known as a particle filter. The key idea of the method is to represent the posterior belief <math>Bel(l)</math>by a set of <math>N</math> weighted, random samples or ''particles'' <math>S = {(s_i | i = 1...N)}</math><ref name=":0" />. A sample set constitutes a discrete approximation of a probability distribution<ref name=":0" />. In MCL the samples are of type <math>\langle\langle x,y,\theta\rangle,p\rangle</math>where <math>x,y,\theta
</math>represent the coordinates on the 2D map and the robot orientation, while <math>p \ge 0</math> represents a discrete probability of the likelihood of the particle<ref name=":0" />.

MCL operates in two steps, the robot ''motion step'' and the ''sensor reading step''.

''When the robot moves'' MCL generates <math>N</math>new samples that approximate the robot's position after the motion command. Each sample is generated by randomly drawing a sample from the previously computed sample set with likelihood determined by their p-values<ref name=":0" />. Let <math>l'</math> denote the position of this sample. The new sample’s <math>l</math> is then generated by generating a single, random sample from <math>P(l|l',a)</math>, using the action <math>a
</math> as observed. The p-value of the new sample is <math>N^{-1}</math>.<ref name=":0" />

''Sensor readings'' are incorporated by re-weighting the sample set, in a way that implements Bayes rule in Markov localization. More specifically, let <math>\langle l,p \rangle
</math>be a sample<ref name=":0" />. Then <math>p \longleftarrow a P(s | l)
</math> where <math>s
</math> is the sensor measurement, and <math>a
</math> is a normalization constant that enforces the sum of all p-values to 1<ref name=":0" />. The incorporation of sensor readings is typically performed in two phases, one in which <math>p</math> is multiplied by <math>P(s | l)

</math>, and one in which the various p-values are normalized.<ref name=":0" />

In practice the introduction of a small number of uniformly distributed random samples at each step is recommended to enable re-localization in the rare event that the robot looses track of its position.<ref name=":0" />

==== Properties of MCL ====
The main property that makes MCL such a powerful algorithm is that it can universally approximate arbitrary probability distributions. The variance of the importance sampler converges to zero at a rate of <math>1/\sqrt{N}</math>(under MCL conditions). This creates a clear trade-off of accuracy and computational load<ref name=":0" />. However, the true advantage lies in the way MCL places computational resources on regions with high likelihood, where things really matter<ref name=":0" /> also known as adaptive sampling. More about this is shown in the second paper description below.

Given there is no [https://en.wikipedia.org/wiki/Discretization discretization] of the space or the data, MCL is able to estimate the state of the robot to any numerical accuracy given sampling size.<ref name=":0" />

MCL is an online algorithm, meaning that it leads itself nicely to an any-time implementation. This means that the algorithm is able to provide an answer at any time, however the quality of the solution increases with time.<ref name=":0" />

=== Pedestrian Localization for Indoor Environments ===
The pedestrian localization problem is the second paper of this page, it builds upon the MCL algorithm and adapts it to the localization of pedestrians in an indoor environment. In particular this paper looks at how a foot-mounted inertial unit, a detailed building model, and a particle filter can be combined to provide absolute positioning, despite the presence of drift in the inertial unit and without knowledge of the user’s initial location<ref name=":1" />.

There are several differences between robot and pedestrian localisation as presented in the paper. Firstly, the robots used in existing literature have been unable to climb stairs. As a result, a 2-dimensional map of the environment has been sufficient. Secondly, the movement of a robot can be actively controlled. This is clearly not possible in a pedestrian localisation system. Thirdly, robot localisation is typically solved knowing both the relative movement of the robot and measurements obtained from a laser range finder. In contrast, only relative movement information is used (in the form of step events) to solve the pedestrian localisation problem.

==== 2.5D Mapping ====
[[File:2.5D map lecture room.png|thumb|315x315px|Illustration of a 2.5D map. It illustrates the way stairs and walls are mapped in the environment.]]
There are many obstacles that limit the possible movement of a pedestrian within a building. In particular walls are impassable obstacles. In order to enforce such constraints it is necessary to have a computer-readable plan of the building. Since it is reasonable to assume that a pedestrian’s foot is constrained to lie on the floor during the stance phase of the gait cycle, a 2.5-dimensional description of the building (in which each object has a vertical position but no depth) is sufficient<ref name=":1" />. Hence a map is defined to be a collection of planar floor polygons.Each floor polygon corresponds to a surface in the building on which a pedestrian’s foot may be grounded<ref name=":1" />. Each edge of a floor polygon is either an impassable wall or a connection to the edge of another polygon. Connected edges must coexist in the (x,y) plane, however they may be separated in the vertical direction to allow the representation of stairs<ref name=":1" />.

==== Tracking using a foot mounted IMU ====
Although we're dealing with tracking people, the MCL is usually applied to robots, where mobile devices typically use inertial sensors, laser range-finders and computer vision to provide accurate localisation without the requirement of fixed infrastructure<ref name=":1" />. Applying the same systems to people is, however, fraught with difficulties; laser range-finders and cameras are impractical, we lose the ability to control the subject to maximize our chances of precise localisation, and the techniques are usually developed with a single floor in mind<ref name=":1" />.

One type of sensor which does seem applicable to people tracking is [https://en.wikipedia.org/wiki/Inertial_measurement_unit inertial measurement units (IMUs)]. An IMU contains three orthogonal rate-gyroscopes and accelerometers, which report angular velocity and acceleration respectively. In principle, it is possible to track the orientation of the IMU by integrating the angular velocity signals. This can then be used to resolve the acceleration samples into the global frame of reference, from which acceleration due to gravity is subtracted. The remaining acceleration can then be integrated twice to track the position of the IMU relative to a known starting point and heading<ref>Titterton, D. H., and J. L. Weston. ''Strapdown Inertial Navigation Technology''. 2nd ed. IEE Radar, Sonar, Navigation, and Avionics Series 17. Stevenage: Institution of Electrical Engineers, 2004.</ref>.

For foot-mounted IMUs the cubic-in-time drift problem can be reduced by detecting when the foot is in the stationary stance phase (i.e. in contact with the ground) during each gait cycle. Zero velocity updates (ZVUs) can be applied during this phase, in which the known direction of acceleration due to gravity is used to correct tilt errors which have accumulated during the previous step. The application of such constraints replaces the cubic-in-time error growth with an error accumulation that is linear in the number of steps.<ref name=":1" />

==== Particle Propagation for pedestrian localization ====
The particle propagation for pedestrian localization closely resembles the update given by the robot motion in MCL, with an exception for determining which floor polygon to which the propagated particle is constrained. Initially it is assumed that the particle resides in the floor polygon it came from. In order for it to exit the floor polygon the step vector must intersect one of its edges in the (x,y) plane. There are three cases outlined by the authors:
# No intersection point is found. The particle must still be constrained to the same polygon.
# The first intersection C is with a wall. In this case the particle’s weight should be set to equal 0 in the correction step, enforcing the constraint that walls are impassable.
# The first intersection C is with an edge connecting to another polygon. In this case we update the current polygon to the new connected polygon.
Since a single step may span multiple connections, the intersection test is repeated between the remainder of the updated polygon. This process continues recursively until one of the first two cases applies.

==== Particle Correction for pedestrian localization ====
The correction step sets the weight <math>w_t</math>of a propagated particle. This step is used to enforce wall constraints. If a wall is intersected during the propagation step used to generate the state of the particle, then it is assigned a weight wt = 0<ref name=":1" />. If a wall is not intersected, the particle is assigned a weight based on the difference between the height change <math>\delta z

</math> of the current step and the difference in height between the start and end floor polygons. The height change according to the map is given by <math>\delta z_{poly} = Height(poly_t) - Height(poly_{t-1})
</math><ref name=":1" />.

Here we are using the change in height reported in the current step as a measurement in the Bayesian framework. Particles whose change in height over the step closely matches the change in height reported in the step event are assigned stronger weights<ref name=":1" />. This allows localisation to occur quickly when the user climbs or descends stairs.
[[File:Algorithm update particle propagation and correction for pedestrian localization.png|none|thumb|787x787px|Algorithm containing particle propagation and correction steps for pedestrian localization. Source: Woodman, Oliver, and Robert Harle. “Pedestrian Localisation for Indoor Environments.”]]

==== Re-sampling for pedestrian localization ====
The number of particles needed to represent <math>Bel(s)
</math>to a given level of accuracy depends on the complexity of the distribution, which can vary drastically over time. As a result it can be highly inefficient to use a fixed number of particles. This is particularly true for localisation problems, where the number of particles required to track an object after convergence is typically only a small fraction of the number required to adequately describe the distribution in the early stages of localisation<ref name=":1" />.

Kullback-Leibler divergence (KLD) sampling is used in this framework since likelihood-based adaptation is not well suited for problems where <math>Bel(s)
</math> can be a multi-modal distribution, as is often the case during indoor localisation due to symmetry in the environment<ref name=":1" />. The idea of KLD-sampling is to generate a number of particles at each step such that the approximation error introduced by using a sample-based representation of <math>Bel(s)
</math>remains below a specified threshold <math>\epsilon
</math>.

Since the propagation step in this framework uses control information (in the form of step events), the propagated belief is a reasonable estimate of the posterior.

=== Contributions and Comparisons ===
Taking MCL and adapting it to a pedestrian tracker requires several modifications. MCL was designed for robot localization, robots can have multiple sensors in them to provide information about the environment. Strapping a laser sensor or camera to an individual can be a difficult demand. For such reason the authors resorted in only using an IMU for localization, which makes localization much more difficult. Given humans move by walking in steps, the researchers exploited the IMU data further by making assumptions on the readings, they included ZVU to understand when a step occurred and assumed all footsteps would be in contact with the floor. This enabled the sole use of the IMU for tracking given the aforementioned assumptions and the expansion of the algorithm to a 3 dimensional environment with the 2.5D mapping trick that was show above.

From the pedestrian adaptation of MCL the main contributions to be carried forward are the concept of expanding the map to higher dimensions and the use of assumptions as constraints to reduce the number of sensors or readings needed to make the algorithm work.

The second paper introduces the use of KLD as a method for adaptive sampling, which may be relevant to general applications of MCL.

It is challenging to compare accuracy in localization for both approaches as environments and data used are very different and the nature of the algorithm in place is stochastic and can be varied in many ways. That said, reported accuracies for experiments for robotics application of MCL fall between 5-10cm with large enough sampling (~1000-10000 samples)<ref name=":0" /> while for the pedestrian application they report an accuracy of 0.5m 75% of the time and 0.73m 95% of the time<ref name=":1" />. It can be seen that the removal of observatory sensors is quite damaging to accuracy even when employing assumptions to the data being generated, although given the limited sensors and large map environment, the results can still be useful for the task at hand (Robot localization applications tend to require more accurate localization as their navigation often depends on it, human can do it themselves).

== Annotated Bibliography ==
[1] Fox, Dieter, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun. “Monte Carlo Localization: Efﬁcient Position Estimation for Mobile Robots,” In ''Proc''.''of the IEEE International Conference on Robotics & Automation (ICRA)''. 1999, 7.

[2] Woodman, Oliver, and Robert Harle. “Pedestrian Localisation for Indoor Environments.” In ''Proceedings of the 10th International Conference on Ubiquitous Computing - UbiComp ’08'', 114. Seoul, Korea: ACM Press, 2008. <nowiki>https://doi.org/10.1145/1409635.1409651</nowiki>.

[3] Titterton, D. H., and J. L. Weston. ''Strapdown Inertial Navigation Technology''. 2nd ed. IEE Radar, Sonar, Navigation, and Avionics Series 17. Stevenage: Institution of Electrical Engineers, 2004.

== 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.