Basic Information

  • Course Code: EE 736
  • Course Name: Introduction to Stochastic Optimisation
  • Course Offered In: 2022-‘23
  • Semester Season: Spring
  • Instructors: Vivek Borkar
  • Prerequisites: EE 325 or EE 601 or an equivalent course on probability and random processes. Markov chains is recommended but not necessary since the instructor covers all the required concepts.
  • Difficulty (1 being easy and 5 being tough): 4

Course Content

1) Stochastic Approximation: convergence analysis of the Robbins-Monro algorithm, theory of ODEs, stability and Liapunov theory (in brief), variations of Robbins-Monro including two time scale schemes, fixed point schemes and probability simplices

2) Markov Chain Monte Carlo (MCMC): Reversible Markov chains, general rejection sampling, importance sampling, MCMC, Gibbs sampling, exact sampling, simulated annealing, and large deviations theory (in brief)

3) Markov Decision Processes (MDPs): controlled Markov chains or MDPs, dynamic and linear programming, value and policy iteration, solutions to infinite-horizon discounted cost, average cost and risk-sensitive cost, and examples including stochastic shortest path and optimal stopping

4) Reinforcement Learning: Q-learning, post-decision state formalism, actor-critic algorithms, TD(0), LSPE(0), policy gradient methods, and Bellman error methods

Additional topics (time permitting)

Feedback on Lectures

The lectures are well-paced, but the instructor tends to digress into other topics, incidents, and short stories. Though interesting, these make the lectures difficult to follow. Asking doubts is crucial to gain a better understanding of the content. The professor shares his slides and encourages students to take their printout for reference during the lecture. The instructor also asked the TAs to conduct help sessions after every major section of the course, which was helpful. Questions from past year papers were also discussed during the help sessions.

Feedback on Evaluations

Evaluation Scheme: Midsem (35%), Endsem (35%), Project (30%) Exams are open notes (another reason why taking a printout of the slides helps). They are not difficult as long as you have revised the content thoroughly. The questions do not require a lot of ingenuity and are applications of the proof techniques discussed. The project involves writing a short report on a topic of the instructor’s choosing based on the content covered in the course. A summary of the assigned paper is expected; salient theorems and proofs may be included. Grading is lenient: AA: 15 , AB: 11, BB: 4, BC: 4, CC: 1

Study Material and Resources

1) Stochastic Approximation: A Dynamical Systems Viewpoint (Vivek Borkar) for the section on stochastic approximation 2) Simulation (Sheldon Ross) for the section on MCMC The references above are only for your interest. Revising the slides is enough.

Follow-up Courses

None

Final Takeaway

This is a fairly mathematical course. Although several complicated proofs are covered, the instructor focuses more on intuition rather than rigour. The content is designed to help you understand the literature in the broad field of stochastic approximation theory and recommended for research-oriented students, especially those who would like to work with Prof. Borkar in the future.