We all know that for software, the most classic definition of the program = algorithm + data structure, the importance of algorithms for software is self-evident. We can even say that the algorithm is the soul of the program. However, as a programmer, you may feel intimidated and frustrated whenever you hear the topic of “dynamic programming.” It’s a scary topic, but it will get you ahead in coding interviews and improve you as a programmer. Today, algo.monster will talk about the three best books that can help you learn dynamic programming better.
[2] How to learn dynamic programming
Studying with books will make you amazed at how easy dynamic programming problems can become because these books give you much confidence and information. However, dynamic programming is a heavy topic, not very sexy, and not very marketable, so, unfortunately, most books are dense and hard to read. Therefore, in the list below, we include books that are well-structured and informative.
[2] The first book
Markov decision processes: discrete stochastic dynamic programming
This book is unique because it brings together, so many results found only in other texts and papers. The text includes actual primary mathematical results and provides many examples, applications, and exercises. The bibliographic material at the end of each chapter is excellent, not only from a historical perspective but also because it is valuable for researchers to gain a good perspective on the potential of MDP research.
It has detailed explanations of several algorithms for MDPs: linear programming, value iterations and strategy iterations with finite and infinite horizons, total and average return criteria, and a final chapter on continuous-time MDPs (SMDPs).
The presentation comprehensively covers this elegant theory, including all significant problems (finite and infinite horizons, discounted rewards, average rewards). The production is rigorous, and while best appreciated by Ph.D. students and the research community, most of the presentation can also be easily understood by a masterful audience with a deep background in probability.
However, it does not cover some new ideas such as partitioning and some faster approximation algorithms. But it is still a great book!
[2] The second book
Dynamic programming and optimal control. Vol. 1.
It is an excellent book and one of the best beginner books on the subject. If you are interested in reinforcement learning/dynamic programming/control, this is a perfect introduction to the topic.
Professor Bertsekas’ book is a significant contribution, providing a 30,000-foot view for practitioners in the first volume and a closer look at specific algorithms, strategies, and heuristics in the second – a vast literature generated by a diverse community of people pursuing the understanding and solution of control problems. It is accomplished by presenting formal models for the particular case of optimal control problems and a comprehensive and detailed synthesis (or survey, perhaps) of the main ideas that constitute the approximation approach. The book ends with a discussion of continuous-time models, which is the most challenging part for the reader.
Each chapter contains several examples that illustrate computational challenges or present major unresolved research questions. In addition, a short but extensive literature review is presented for each covered topic at the end of each chapter.
It is a book that is both quite impactful and will provide you with substantial benefits. Graduate students looking for challenges and deepening their understanding will find this book helpful. Ph.D. students and postdoctoral researchers will find Prof. Bertsekas’ book an instrumental reference book. They will return time and time to find obscure references to related work, use one of the examples in their papers, and draw inspiration from the deep connections between effective techniques. Undergraduates should try the online lectures first and decide if they are ready for them.
[2] The third book
Decision Theory: An Introduction to Dynamic Programming and Sequential Decisions
If your main interest is in dynamic programming algorithms and applied probability, this book is almost perfect. The focus is on dynamic programming applied to discrete optimization problems, including all the usual goodies (shortest paths, Knapsack, optimal stops, etc.) and some continuous models. The exposition is driven by worked examples rather than by theorems and proofs. The style of the book is precise but straightforward and practical – effortless to understand. How it covers so much in just 200 pages is remarkable.
John Baser’s book does not exaggerate its title. It is an introductory book that focuses primarily on the basics of dynamic programming.
You will likely absorb more information as you do it than just read about it. The teaching style of the book reflects this. In addition, the book provides many practice problems and explains all the techniques needed to solve problems.
As a bonus, the author’s fluid style does an excellent job igniting avid interest in the subject. Here are some highlights of the textbook.
Suitable for learners of decision theory and optimization theory
Written in a conversational style with many applications and examples
Deterministic models: scheduling, convexity, utility maximization, directed networks, critical path analysis, and shortest paths
Stochastic models: optimal stopping problems, stochastic dynamic issues, and other special topics
Advanced topics: expected cost minimization, policy improvement, problems with unknown statistical parameters, and Markov decision processes
Includes practical exercises as well as tips and explanations
Although the book is primarily for students of statistics and mathematics, its content will also appeal to engineering students, science students, and students working in optimization and operations research.
[2] Final Thoughts on dynamic programming
Don’t give up on dynamic programming! All dynamic programming algorithms is just seeming frustrating at first. But when you have these books by your side, learning is more manageable and more accessible.
After some time spent reading any of the books listed above, along with some practice, writing dynamic programs will naturally come to you. I hope you’ve found this list helpful in making your learning better on dynamic programming, and if you need more help, don’t hesitate to get in touch with us and go for more professional programs.
