STATS 710: Sequential Decision Making with mHealth Applications

Fall 2016

Grading

Topics

Schedule

Readings

Projects

Class Information

Days & Time: Tuesdays and Thursday, 3:30-5:00pm (exceptions noted below)
Location: Till September 20: 4246 Randall Hall. September 22 onwards: 1450 ISR (but we’ll use 4246 Randall on a few days; see below). ISR is located at 426 Thompson Street
Description: Mobile health offers us an unprecedented opportunity to help people with long-term health behavior change. Smartphones and wearable devices have remarkable sensing capabilities allowing us to understand the context in which a person is at a given moment. These devices also have the ability to deliver interventions tailored to the specific needs of users in a given location at a given time. Figuring out which interventions lead to improved health outcomes for which people in what contexts is a fundamental decision making problem in mobile health. This advanced level graduate course will focus on theory and algorithms for sequential decision making algorithms with an emphasis on mobile health applications.
The course will cover the following topics: (1) multi-armed bandit problems, (2) contextual bandit problems, (3) reinforcement learning in MDPs (Markov Decision Processes), and (4) special topics of interest in mobile health applications. Subtopics in the last category might include transfer learning (using data on other similar people to enable faster learning), non-stationarity (dealing with slowly changing or abrupt changes in user behavior), interpretability of policies (enabling communication with behavioral scientists by making connections to behavioral theories), computation/communication tradeoffs (one-the-phone vs in-the-cloud computations), myopic/long-term planning tradeoffs (myopic approaches can be more lightweight, both computationally and with regards to theoretical analyses, but ignore impact of our interventions on future user contexts), and user engagement (a large fractions of health apps are abandoned after a small number of uses).
Textbook: No textbook is required for this course.
Canvas: We will the Canvas learning management system for this class. We will use the Canvas website for this class to make important announcements, get feedback from students, and store course related resources.

Instructor Information

Name: Susan Murphy

Office: 445D West Hall

Office Hours: By appointment

Email: samurphy@umich.edu

Name: Ambuj Tewari

Office: 454 West Hall

Office Hours: By appointment

Email: tewaria@umich.edu

Grading

This is an advanced graduate level course. Our expectation is that you will engage in the course out of intellectual curiosity. The formal course requirements will be rather minimal. The final grade in the course will be determined by the quality of your scribed lecture notes and one final project using the weights given below.

Scribing Lectures (60%): Each of you will scribe 1-2 lectures. This means taking notes during class and typing them up in LaTeX. The scribed notes will be posted on the course webpage.

Sign up for scribing lecture notes via Canvas->Collaborations->Scribing Schedule
Download the template, useful macros, and the bib file.
Modify the template and fill it with your notes.
If you make additions to the macros or bib file, make sure to do that at the very end.
For bibtex entries, try using Google Scholar. Search for the paper you want to cite, click on “Cite” and then click on “Bibtex” in the window that opens.
Email me your notes with name lecXX.tex (where XX is the lecture number) along with macros and bib files in case you made additions to those.
Look at tex files from other lecture notes and try to keep your notation and style consistent with earlier ones.

Final Project (40%): An important component of the course is a final project which can either be:

a survey of some actively developing sub-topic within sequential decision making, or
a detailed commentary on a classic paper on sequential decision making, or
a research project involving contributing novel research (theoretical result, statistical method, computational algorithm) to the area of sequential decision making

Project credit breakup: Surveys have to be written individually. However, teams of up to 2 students can be formed for a research project. To get full credit, surveys have to be very high quality: they should be similar to a publishable survey article in a top journal. The bar for research projects will be lower because of the time constraint and the inherent uncertainty in the research process. While you’re not required to deliver publication quality research work by the end of the semester, you’re encouraged to do so. We will provide some suggestions for research projects but you should feel free to work on any problem that interests you. The 40% credit for the project will be split as follows:

Project proposal (5%)
Project poster presentation in class (10%)
Project final report (25%)

Topics

A tentative list of topics is as follows.

Multi-armed Bandits: regret analysis, major algorithm families (phased exploration with greedy exploitation, upper confidence bounds, posterior sampling aka Thompson sampling), adversarial setting (Exp3 algorithm)
Contextual Bandits: regret analysis in three settings (stochastic contexts & rewards, adversarial context & stochastic rewards, adversarial contexts and rewards), parametric (LinUCB and Thompson Sampling with Gaussian linear model) and nonparametric modeling of reward functions, competing with policies (Exp4, epoch greedy, RUCB, ILOVETOCONBANDITS)
Learning in MDPs: Basics of MDPs (value functions, Bellman equations, value iteration, policy iteration, need for function approximation in real world problems), theoretical analysis of learning in ``small” MDPs: PAC-MDP literature (Rmax, MBIE, Delayed Q-learning, MorMax) and regret bounds (UCRL2), fundamental learning algorithms for practical problems ([gradient] temporal difference methods, least squares methods, policy gradient methods, actor-critic methods)
Challenges in Mobile Health: costly to acquire features (EMAs), non-stationarity, good initialization of policies, interpretability of policies, computational considerations on the phone, missing data, user engagement

Schedule

Lecture number	Day \| Notes	Topics
1	Sep 06 \| lec01.pdf	Course logistics Introduction to Multi-armed bandits Basic consistency result from Robbins (1952)
2	Sep 08 \| lec02.pdf	Epsilon greedy and its regret analysis from Auer et al. (2002)
3	Sep 13 \| lec03.pdf	Non-standard time 2:30-4 Finish regret analysis of epsilon-greedy UCB and its regret analysis from Auer et al. (2002)
4	Sep 15 \| lec04.pdf	Non-standard time 2:30-4 Finish regret analysis of UCB
5	Sep 20 \| lec05.pdf	From gap based distribution specific to distribution independent regret bounds Distribution independent lower bound (informal version) Thompson sampling for Bernoulli rewards with Beta priors
6	Sep 22 \| lec06.pdf	Regret analysis of Thompson Sampling from Agrawal and Goyal (2013)
7	Sep 27 \| lec07.pdf	Finish regret analysis of Thompson Sampling
8	Sep 29 \| lec08.pdf	Non-stochastic bandit problem and the Exp3 algorithm from Auer et al. (2002)
	Oct 04	CLASS CANCELLED Initial project proposals due
9	Oct 06 \| lec09.pdf	Finish regret analysis of Exp3 Introduction to contextual bandits
10	Oct 11 \| lec10.pdf	In old location: 4246 Randall Competing with a class of policies Reduction to multi-armed bandits (finite context space)
11	Oct 13 \| lec11.pdf	Epoch Greedy algorithm from Langford and Zhang (2008)
12	Oct 18 \| lec12.pdf	Exp4 algorithm from Auer et al. (2002) Final project proposals due
13	Oct 20 \| lec13.pdf	VE algorithm and regret analysis from Beygelzimer et al. (2011)
	Oct 25	NO CLASS
	Oct 27	NO CLASS
14	Nov 01 \| lec14.pdf	Lecture by Susan Introduction to RL; transitioning from contextual bandits
15	Nov 03 \| lec15.pdf	Lecture by Susan UCB for finite horizon RL from Auer & Ortner (2005)
16	Nov 08 \| lec16.pdf	In old location: 4246 Randall ILOVETOCONBANDITS from Agarwal et al. (2014)
17	Nov 10 \| lec17.pdf	Lecture by Susan UCB for finite horizon RL from Auer & Ortner (2005) Susan’s notes
18	Nov 15 \| Slides from Elad’s talk	Non-standard time 2:30-4 Guest lecture by Elad Yom-Tov
19	Nov 17 \| lec19.pdf	PAC bounds for multi-armed bandits from Even-Dar et al. (2002)
20	Nov 22 \| lec20.pdf	Finish analysis of Median Elimination from Even-Dar et al. (2002)
	Nov 24	THANKSGIVING BREAK
21	Nov 29 \| lec21.pdf	Online ranking with top-1 feedback from Chaudhuri and Tewari (2015) An instance of a partial monitoring game with a combinatorially large action space
22	Dec 01 \| lec22.pdf	Online ranking with top-1 feedback (continued) Non-standard time 4-5
23	Dec 06 \| lec23.pdf	Guest lecture by Nan Jiang Nan’s slides Contextual decision processes with low Bellman rank
24	Dec 08 \| lec24.pdf	Guest lecture by Nan Jiang Contextual decision processes with low Bellman rank
	Dec 13	Location: East Conference Room 4th floor Rackham Building Poster Setup: 3-3:30 Poster Presentations: 3:30-5:00
	Dec 14	Project reports due
	additional01.pdf	Note: A Reinforcement Learning System to Encourage Physical Activity in Diabetes Patients
	additional02.pdf	Note: Risk-Averse Bandits
	additional03.pdf	Note: Bandits with heavy tailed distributions

Readings

Books and Monographs

Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Now Publishers, 2012.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
Csaba Szepesvári. Algorithms for Reinforcement Learning. Morgan and Claypool Publishers, 2010.

Bandit Problems

Herbert Robbins. Some Aspects of the Sequential Design of Experiments. Bull. Amer. Math. Soc., Volume 58, Number 5 (1952), 527-535.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, Volume 25, Number 3/4 (1933), 285-294.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, Volume 47, Number 2-3 (2002), 235-256.
Shipra Agrawal and Navin Goyal. Further Optimal Regret Bounds for Thompson Sampling. AISTATS. 2013.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, Volume 32, Number 1 (2002), 48-77.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and Markov decision processes. In International Conference on Computational Learning Theory, pp. 255-270. Springer Berlin Heidelberg, 2002.

Partial Monitoring

Sougata, Chaudhuri and Ambuj Tewari. Online Ranking with Top-1 Feedback. In AISTATS. 2015.

Contextual Bandit Problems

John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems, pp. 817-824. 2008.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual Bandit Algorithms with Supervised Learning Guarantees. In AISTATS, pp. 19-26. 2011.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits. In Proceedings of The 31st International Conference on Machine Learning, pp. 1638-1646. 2014.

Learning in MDPs

Peter Auer and Ronald Ortner. Online regret bounds for a new reinforcement learning algorithm. In Michael Zillich and Markus Vincze, editors, 1st Austrian Cognitive Vision Workshop, pages 35–42. Austrian Computer Society, 2005.

Overviews of mHealth

William T. Riley, Daniel E. Rivera, Audie A. Atienza, Wendy Nilsen, Susannah M. Allison, and Robin Mermelstein. Health behavior models in the age of mobile interventions: are our theories up to the task? Translational Behavioral Medicine 1, no. 1 (2011): 53-71.
Santosh Kumar, Wendy J. Nilsen, Amy Abernethy, Audie Atienza, Kevin Patrick, Misha Pavel, William T. Riley, Albert Shar, Bonnie Spring, Donna Spruijt-Metz, Donald Hedeker, Vasant Honavar, Richard Kravitz, R. Craig Lefebvre, David C. Mohr, Susan A. Murphy, Charlene Quinn, Vladimir Shusterman, Dallas Swendeman. Mobile health technology evaluation: the mHealth evidence workshop. American Journal of Preventive Medicine 45, no. 2 (2013): 228-236.
Steven R. Steinhubl., Evan D. Muse, and Eric J. Topol. Can mobile health technologies transform health care? JAMA 310, no. 22 (2013): 2395-2396.
Santosh Kumar, Wendy Nilsen, Misha Pavel, and Mani Srivastava. Mobile health: Revolutionizing healthcare through transdisciplinary research. IEEE Computer 1 (2013): 28-35.
Inbal Nahum-Shani, Shawna N. Smith, Bonnie J. Spring, Linda M. Collins, Katie Witkiewitz, Ambuj Tewari, and Susan A. Murphy. Just-in-Time Adaptive Interventions (JITAIs) in Mobile Health: Key Components and Design Principles for Ongoing Health Behavior Support. Annals of Behavioral Medicine (2016): 1-17.

Projects

Aniket Deshmukh: Contextual Bandits Upper Confidence Bound Algorithms
Anurag Beniwal: Personalized problem assignment in Problem Roulette
April Cho: Limitation of the algorithms that separate exploration from exploitation
Brandon Oselio and Henry Oskar Singer (with Walter Dempsey): Reinforcement Learning with Network Interference
Brook Luers: EXP3 and missing rewards
Huajie Qian: Gradient-free algorithm for stochastic bandit problem on probability simplex
Hyesun Yoo: Application of bandit algorithms in clinical trials
Ian Fox: Deep Q Learning, Bootstrapped Thompson Exploration, and the OpenAI Gym
Julie Deeke: Contextual Bandits as Learning Assistants for Academic Courses: A simulation study
Lauren Steimle: Learning in Contextual MDPs
Nick Seewald: Advances in Model-Based Reinforcement Learning
Peng Liao and Timothy Necamp (with Walter Dempsey): Multi-armed bandits for network-cohesion
Young Hun Jung: Online Multi-class Boosting with Partial Feedback
Yutong Wang: Guiding message-passing algorithms using reinforcement learning