Hacker News new | past | comments | ask | show | jobs | submit login
Algorithms for Decision Making (algorithmsbook.com)
693 points by Dowwie 6 months ago | hide | past | favorite | 85 comments



This looks neat, but anyone interested should know there's also a whole mature field to solve similar problems. The field of control theory has some really simple and really robust methods for getting a system from state A to state B. If you aren't trying to learn how the system works simultaneous to your algorithm being deployed, it can be a really a good fit.

This book and control theory solve different problems. I'm just commenting because I sometimes see modern ML folks trying to apply super duper general techniques to problems that are easily solved specifically with simple undergrad-level techniques from the specific fields (including this material to control problems). Also, I just think control theory is really cool and perhaps under-discussed in "cool math/eng stuff" circles.


You are right that sometimes people use much more sophisticated algorithms than are really required to solve a problem. My experience is that the simplest approach is often the best one in the long term. There are actually deep connections between problems in control theory and the topics in this book (e.g., LQR control), though these different communities often use different notation. The focus of the book is more on higher-level decision making, but the execution of the decisions---such as motor commands to an actuator---are often best done through PID or some other method that can be found in a control theory textbook.


Control theory is indeed, quite cool, and under-discussed in most circles.

Also, unfortunately, classical control theory is primarily good for linear time-invariant dynamics in the frequency space of the Laplace transform. If you can't locally linearize your model and/or need to learn a model, classical control approaches are underdeveloped, and everyone has switched to optimal control and RL.


I think you might mean something different by optimal control than I would. I'd bucket that into control theory, but it seems you're drawing a distinction.


I would distinguish between classical control and optimal control. In the former, you don't have a (Hamilton-Jacobi-)Bellman equation to solve, while in the latter, the approximate dynamic programming is The Hard Part.


This is neat - specifically because what you point out is actually true. The primary author is a professor and the secondary author is a Phd graduate - both in the Stanford Aeronautics and Astronautic Department [1][2] - in the Dynamics and Control Group.

A brief skim through of the book shows many references to Control Theory texts.

[1] https://mykel.kochenderfer.com

[2] http://timallanwheeler.com/aboutme/cv/Wheeler_CV_201804.pdf


That explains why there is not as much traditional Decision Theory in the book as one would expect from the title, such as Peter C. Fishburn's work, issues in MAUT and MCDM, seminal work by Bouyssou, Vincke, Pirlot, Keeney, or the older discussions about SEU vs. EU, evidential vs. causal decision theory, etc.

It's a rather technical book, focusing on issues like advanced sensor data fusion, control theory, and optimization. Not that there is anything wrong with that, the title is just slightly misleading.


For control theory from a mathematician, Fleming, long at the Division of Applied Mathematics at Brown University, there is:

Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control, ISBN 0-387-90155-8, Springer-Verlag, Berlin, 1979.

There is more on optimization, especially from the Hahn-Banach theorem, and also Kalman filtering, in

David G. Luenberger, Optimization by Vector Space Methods, John Wiley and Sons, Inc., New York, 1969.


Can you recommend any good books or other resources?


Ben Recht [0] has worked on control theory and reinforcement learning.

See his blog post "What we've Learned to control" [1] and the survey paper "A Tour of Reinforcement Learning: The View from Continuous Control" [2] may be of interest.

[0]: https://people.eecs.berkeley.edu/~brecht/

[1]: https://www.argmin.net/2020/06/29/tour-revisited/

[2]: https://arxiv.org/abs/1806.09460


I learned it from a course where my professor had his own notes printed by the school bookstore for us, and I've held onto those notes like they're gold. So I can't refer you anything by firsthand knowledge, but the internet seems to like Dorf & Bishop's Modern Control Systems, which seems like a decent coverage of the basics:

https://smile.amazon.com/Modern-Control-Systems-13th-Richard...


After the basic PID controller, what would you consider the most useful tools for control?


the next step after PID control is state-space based control.

it's not a single tool but more of a framework. it goes beyond frequency based representations and can also model non-linear control problems.

the kalman filter is an example of the use of this framework where it's combined with statistics.

the problem in control theory though is that once you want to go beyond linear control things get very difficult, most of the literature seems to be about finding clever ways of approximating your problem into something linear.


Check out model predictive control. And LQR if you haven’t learned that yet. And the bazillion state estimation techniques that start with Kalman filtering variants (eg UKF) and progressively account more and more for nonlinearities.


I know virtually nothing about control theory, but when I was into RC quadcopters back around 2011 I know Kalman filters got name dropped a lot.

https://en.wikipedia.org/wiki/Kalman_filter


Kalman filters and variations are covered in Ch. 19. It can be viewed as a special case of belief updating in a partially observable Markov decision process.


I can also recommend "Algorithms to Live By", by Brian Christian & Tom Griffiths. https://www.amazon.com/Algorithms-Live-Computer-Science-Deci...

Super accessible.


I recommend that one to my students. I also recommend Brian's new book titled "The Alignment Problem" and it is cited in the book.


I still think about this book every time I get on Zillow. Great chapter on buying a home.


Yeah, that was a really great book. Also has a well-produced narration available on Audible that I listened to. I recommend it.


I bumped into this accidentally having ever heard of it. It is one of those pleasures of browsing through a library. Lovely book, easy to understand with a broad range of topics and insights. Recommended!


Just started reading this thanks to your recommendation, it looks like a really entertaining book, thanks!

PS for others, it's on libgen...


Shh.. first rule of *


I love this book. Listened to it 4-5 times. Lots of really practical application


Such a good book. I learned so much about life from the multi-armed bandit problem.


Reading this at the moment! Fantastic book and easy to read


Yes! ATLB is fantastic!


The title reminded me of this anecdote (which I can't locate now, might have been somewhere in Kahneman's or Ariely's recent oeuvre):

This associate professor of Decision Theory received two offers of tenure track positions at reputable universities, and got some friends and colleagues together to discuss which one to take. One of them suggested he use the tools of his discipline, Decision Theory, to help him make a decision. To which the professor replies: "Now, come on guys, this is serious..."


I link at the source of this anecdote at the end of my essay on I-Ching: https://www.pa-mar.net/Lifestyle/I-Ching.html

Here is the direct link if you don't care about my stuff (it has been featured on HN already)

http://statweb.stanford.edu/~cgates/PERSI/papers/thinking.pd...


Thanks for that source, a talk by frightfully brilliant Stanford mathematician and magician Persi Diaconis. It contains another cute anecdote:

> One of my most endearing memories of the great psychol- ogist of decision making under uncertainty, Amos Tversky, recalls his way of ordering in restaurants: “Barbara? What do I want?”


;) the whole piece is really a fantastic read.


The first author (MK) also wrote "Algorithms for Optimization" (MIT Press), which is also implemented in (and is a nice guide to) the Julia language, which is itself a pretty sweet language.


*first two authors (MK and TW) wrote Alg4Opt This new book is in the same format.


I highly recommend this book. I am 100% going to buy their next book too.

Julia is an awesome language and the ecosystem around it is getting better quickly.


Does anyone have any advice on how to make the most out of books like these? I'm trying to read more textbooks in subjects that I really phoned in during college this year. My current strategy is to make some note cards and take notes (which is kind of tedious), wondering if anyone has any advice as to their own workflows.


My suggestions, not for this book in particular but technical textbooks in general:

- Get very familiar with the table of contents first. Then note and filter out the sections you are less interested in or don't appear to provide the biggest bang for your buck.

- Annotate, annotate, annotate. Active reading is better than passive reading. I use a 2-in-1 chromebook and a passive pen to highlight in the adobe pdf reader.

- Write detailed notes in addition to annotating (i.e. in a separate notebook or markdown file). Cull/convert your notes into Anki/Memrise digital flashcards. Drill on your phone when you are lying in bed.


As a programmer I usually try to implement some of the algorithms in language of my choice and throw them at some toy problems (it's good there is no shortage of interesting toy problems in this field). It was really fun with Artificial Intelligence: Modern Approach book (ex: implementing a SAT solver from scratch and solving Minesweeper by pure logic is very satisfying).


The way I did this with a stats book was:

  1. Ten pages a day
  2. Do all the exercises, and redo all the ones you get wrong.
  3. Add anki cards for all the key terms, ideas, formulas, etc. The best textbooks include a summary the end of every chapter that you can double check your notes / anki against. Prefer cloze markup to question / answer cards -- more cards per "fact" but longer retention.
  4. Double check your cards against a source like Wikipedia for completeness / accuracy, since sometimes there's an author bias to content with.
This takes about an hour a day for #1 and #2, and an hour a week for #3/4 plus a few minutes a day extra in the Anki review queue. For this book, you're looking at about 2 months start to finish.


Get in a group. Work is a good place to do this. Pick out some books, send a mail round saying that you are running a tech book group. Get folks together and read a chapter a week (this is hard in reality - be cool with everyone and sometimes let chapters slip over a few weeks). Every week someone leads the discussion. Every week someone volunteers to do the next weeks. You meet for an hour to discuss.


I enjoy typing, so I like to simply type out the entire textbook. It's a bit ridiculous to some, but it slows down the pace that I actually learn and engage with the content. A textbook usually takes me a couple months to type, and I'm never in a rush though finishing chapters is satisfying and an easy goal for an evening. I find it similar to as if I were to attend a lecture on the topic.


David Goggins makes the claim that due to his learning disabilities he acquired the diving instruction manual 18 months ahead of time and wrote it out by hand 10 times in order to learn the material.

Thought that was really interesting.


Seems like a really bad way to learn.

But gotta love goggins, dude likes taking the hardest path to success.


I guess he had to do it that way in order to be able to learn it at all.

Quite a remarkable level of determination.


For people whose first language is not English maybe translating the book could be a good substitute (never tried this approach personally though)?


As somsone who's currently trying to translate an instruction manual from one language to another, it is... somewhat fragmentary. Yes, you read the text, multiple times (and in multiple languages).

But, the focus is not on internalising the material, the focus is on producing something that makes sense in a different language.

I guess part of the problem is that the source material I am working from is from 1596, in blackletter, and pretty archaic "source language", so the actual process is "transcribe original", "translate transcription".


it's hard for me to learn something if i don't have something I need to do with the knowledge. it's not that I can't sit down and do it, but things won't stick in my brain.

so I would say, try to find something you want to do that requires the information in the textbook. or else just don't bother reading the textbook and go do something else you actually want to do.


Anki is basically the most efficient method to study facts. I use a gamified version called Memrise.


I typically take a book like this and read it. Then I think about it. I also think about it as I read it. I ask my friends in person and online if they've read and talk with them about it. Sometimes I'll look for online forums which discuss the book. This is how I make the most out of books like these.


Anki can be a supercharger, if you have notes that are clear and concise.


This looks very good from my skim! It includes state-of-the-art approaches like Actor-Critic with MCTS and loads of recent and interesting things like GAIL and SMILE. The areas where I have expertise superficially seem like good treatments. I'll have to see what other RLers think and perhaps use it to study up on belief states :)

Much more up-to-date than sutton and barto, but the authors are rather less well known.


Mykel Kochenderfer is my uncle! He does some really cool research up at Stanford. Lots of autonomous quadcopter drones doing automatic maneuvers and learning how to not crash into each other. It’s cool to get to see his work on HN!


Since you had an Ask HN regarding machine learning resources, and your uncle has written some machine learning papers, have you considered asking him to teach you or is he really busy?


I have talked to him about it, actually! He gave me some great course recommendations that I plan on looking into. Ask HN was mostly motivated by wanting to get multiple data points/opinions.


Julia Notebooks containing the source code from the book is available at https://github.com/sisl/algforopt-notebooks


Looks like a different book, "Algorithms for Optimization", by two of the three authors of "Algorithms for Decision Making".


I dont know about you, but I have been trying to cover this topic for some time, but it is very difficult to assimilate. Like many, i am a self learned developer, I do have higher education in sciences and the math is tough to me but I can understand what they are talking about. Still those algorithms are challenging


Anyone who likes this would enjoy George Polya's short book. "How to Solve it" which these days is widely available as a pdf.


I took CS238 (decision making under uncertainty) with the first listed author of this book (Mykel J. Kochenderfer).

It was one of my favorite courses, and it looks like this textbook is now used for that course:

https://web.stanford.edu/class/aa228/cgi-bin/wp/


How is something so useful so available? Is it the karma from past year?


Any way to get an epub version so I can load on Kindle with navigable chapters?


this book describes the linear programming formulation for finding the optimal value function. cool to see, I think this formulation is underrated by the CS community compared to other communities also trying to solve MDPs.

however I wish it also described the dual of this linear program. this problem involves optimizing over state-action frequencies which is equivalent to optimizing over policies.

so value functions and policies are dual to each other. that's pretty neat! not sure why modern RL texts don't talk about it at all.


Thank you for posting this. I think the titel is a bit misleading. When reading "Decision making under uncertainty" I would expect some follow up on Decision Theory by Kahnemann, Keeney, Roy and Brans and methods considering uncertaity in e.g. AHP, Electre, PROMETHEE etc.


Incredible depth and clarity!

Authors, if you're reading this, thanks a thousand for making this available to us!


Sure thing! We wanted to get feedback from the broad community so that we can make it as awesome as possible before it goes to print. ;-)


Looks very good. Can’t believe we can just download the entire pdf free of charge. So helpful !


The authors plan to have the book be free, online, forever!


In some ways this touches on some of the same issues raised in Superforecasting by Philip Tetlock and Dan Gardner. Really interesting to think that we could methodically make better predictions and decisions and potentially greatly improve our society and quality of life.


Would love to have a kindle version.


I think Calibre can convert from pdf to kindle format


Such great resource! Huge props to the authors for making this freely available.


Is a print version of this book available or planned for the near future?


A print version is planned with MIT Press for release in the fall! PDF will continue to be available for free forever.


Thanks a lot! That's great. With a book like that I prefer a printed version.


Lets say I wanted to verify a student read a page of text from a novel. And I wanted to automatically generate a question from that text. Any algorithms that can currently do that?


If you wanted to do Cloze questions, you can use saveall.ai (a tool that I built) to generate them automatically from fragments of texts. We also plan to work on automatically generating questions from a larger chunk of text, but it is very difficult. Some people have had some success with GPT-3 but it's unreliable


Thank you for this book


Thank you. I’ve been hoping for a book like this for a while.


helpmedecideplease.com


At first sight an amazing book, thank you!


This looks awesome. Thank you!


It's a minor nitpick, but anyway, what's up with naming your pdf files like this 'dm.pdf'? What's wrong with 'Algorithms_for_Decision_Making.pdf' of even adding the 'Mykel_Kochenderfer,Tim_Wheeler,Kyle_Wray_-_' prefix? I can't put a proper name in a "save" dialog until I open the book, and I need to save it first!

I sound so annoyed because I recently downloaded 'hist.pdf', 'fxtbook.pdf' and 'V090212S.pdf' Is it just to get a memorable file URL? If so, humanity invented simlinks long ago.


Wild guess is that the main document LaTeX file is called "dm.tex", so the resulting PDF would be called "dm.pdf".

Making the main file named something more verbose would impact you whenever you try to open it, but in an ideal world, you'd rename it once it gets to the point of it not needing many changes.


I very much doubt that the book ends up on a web server as a result of some LaTeX-CI rather than being uploaded by a person.

I'm trying to be considerate and provide a uniquely identifiable file name whenever I make some available to the public. In my opinion, books require the full name and revision, and, as I've already mentioned, you can have a link to it (or a copy) with a short name if you'd like to have an option of a short URL for verbal link transmission.



This is a very important dimension. See Sec. 1.5 of the book. There is also a side reference to a book that discusses this and other societal implications.




Applications are open for YC Winter 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: