Make Smarter Decisions Faster (with Dynamic Programming)

[@Svorls]

its 11pm, and i just binged watch every video from your channel. I thought I'm watching a 100k+ subscribers channel.. It took me like 4 video to notice how awesome your content is compared to the number of views. Please, as a data analyst student and tech enthusiast, continue, you have an enormous potential!

[@RiskByNumbers]

@Svorls: thank you so much for the kind note! I sincerely appreciate your words of encouragement and interest in the channel. Best of luck as well with your current studies!

[@guscastilloa]

Can't believe how well explained a concept like this was! Kudos! Cant wait for the series to start! I'm an economist and analytical methods in dynamic programming make it hard to see what's going on algorithmically, thanks!

[@RiskByNumbers]

Thanks, @guscastilloa. I really appreciate the kind words. I'll be returning to this series shortly. My goal is to wrap up this week a video around why we use natural logs so frequently for economic/financial data. Really appreciate again the kind words, and I'm glad that it was helpful!

[@kevon217]

Great visuals and explanations.

[@RiskByNumbers]

Thanks, @kevon21, for the kind note!

[@mayanksharma6622]

Waiting for more such videos

[@RiskByNumbers]

Thanks, @mayanksharma6622, for the positive note! Slowly making my way towards making similar content on sequential decision-making (e.g., reinforcement learning). Putting together a blog in the meantime as it takes quite a bit of time to make these videos. I appreciate the patience!

[@mrvincefox]

2minutes in and I subscribed..

[@RiskByNumbers]

Hahaha, thanks @mrvincefox! Really appreciate both the subscription and kind words!

[@milkandhenny]

Fantastic, Thank you.

[@RiskByNumbers]

Thanks!

[@zain_x_alpha]

thanks for this and please make more video about programming using charts and animations✨

[@RiskByNumbers]

Thanks, @zain_x_alpha! I'm pushing to get the next one out this Sunday (trying to avoid having it be delayed anymore)!

[@zain_x_alpha]

@@RiskByNumbers thank you😊

[@maloukemallouke9735]

perfect clear

[@RiskByNumbers]

Thank you!

[@kitgary]

Brings me back my terrible programming interviews experience by failing to solve those dynamic programming problems.

[@RiskByNumbers]

Thanks, @kitgary, for commenting on the video. Your comment reminded me of some of my unsuccessful interviews, too, that I must block from memory. I sincerely hope that things have worked out for you, and best of luck with your future endeavors.

[@TBit256]

Great video! Very informative and easy to understand. Really enjoyed the presentation style and your format. Kind of felt like I was back in Data Structures and Algorithms, and I say that as a compliment!

[@RiskByNumbers]

Thanks a lot, @TBit256, for the kind comment!

[@Yupppi]

Why is this called dynamic? Looks extremely static in terms of you narrow down all the combinations to a couple static routes. Furthermore since we're talking about travelling, it's not hard to draw a parallel to having parallel actions, multiple accesses at the same time. This way we're always directing the entity travelling the path to the same nodes and creating bottlenecks with no dynamic ability to reguide. In case of thinking a person taking public transportation it would kinda work in terms of the vehicle always travelling the route independent from the person - until everyone is guided to the same public transportation lines and the vehicles get too full to allow us. Like for a trivial answer this seems great but is it scalable to actual dynamic situations? That questioning aside, such a simple and effective method. Thanks for that, I think it'll be beneficial outside programmin as well. I'd call it reverse iteration or something rather than dynamic though.

[@RiskByNumbers]

@Yupppi: thanks for the thoughtful comment. Your post motivated me revisit Richard Bellman's autobiography, where he recounts the origin of the term 'dynamic programming'. It has quite an entertaining origin: "I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, 'Where did the name, dynamic programming, come from?' The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research... You can imagine how he felt, then, about the term, mathematical… Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying - I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it's impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities."

[@RiskByNumbers]

Entertainment aside, I do think that the idea of 'dynamic' decision-making in the term really shines through when uncertainty is present. The problem in this video assumed a deterministic world. The follow up will touch upon how we can extend these dynamic programming principles to solve problems where it is uncertain where we will end up in each stage.

[@abhinavprabhakar455]

subscribed. awesome channel! Please keep uploading more videos

[@RiskByNumbers]

Awesome, @abhinavprabhakar455! The goal is at least once every 4 weeks during the academic terms, with more frequent posting during the holiday and summer breaks. We have our next break starting in a couple of weeks, and so I'll take advantage of it to produce more content. Really appreciate the positive feedback!

[@abhinavprabhakar455]

@@RiskByNumbers thanks!

[@beeasy247]

Subscribed. Adding the raw data, formatted as JSON, would be helpful for people that want to try coding a solution to the same problem you show.

[@RiskByNumbers]

Thanks, @beeasy247, for subscribing! Yes, the plan is to make a video showing the implementation of the solution and posting the accompanying code as part of the mini-series. I sincerely appreciate the feedback.

[@benjaminarias1350]

Very well explained, thank you

[@RiskByNumbers]

Many thanks!

[@abdelazizelhayyany6087]

What a video I like it but i like the effort and time more Thank you

[@RiskByNumbers]

Thanks, @abdelazizelhayyany6087, for the kind words. It is particularly nice to get a notification like this one as I'm putting together the next video! Thank you.

[@НиколайХанзо]

good vid bud

[@RiskByNumbers]

Sincerely appreciate the note.

[@academyofuselessideas]

Cool! Perhaps the easiest way to share your code is to just open some git repo and share the link. It would have been nice to see why the greedy algorithm does not work for this problem, or in general, to think of the natural ideas that a viewer would have and explore whether they work or not... It is also interesting to explore how large you can make the problem before your code crashes. I have found that almost everyone knows that the Traveling Salesman Problem is "unsolvable" but most people don't know how big it needs to be to become unsolvable (or under which conditions we can find good solutions...)

[@RiskByNumbers]

Yes! I've set up a GitHub page (github.com/RiskByNumbers) for the channel where I am (very slowly) populating it with the codes/datasets used for videos and adding the link to the description once it is cleaned up with commenting. Our school has a couple of weeks remaining in the academic term -- once we are on break, my aim is to be much more timely. Your suggestion is really good in terms of clarifying when the problem becomes too large to solve. Let me think through whether there is a nice way to touch on this in either of the 2 upcoming videos that I'm putting together around sequential decision making.

[@academyofuselessideas]

Looking forward to the next!... The first realization is: np complete problems cannot be solved... then eventually you realize: Oh, all problems i want to solve are np complete, so better find a way to deal with them in real life... Approximation algorithms become a necessity... but it is also worth to have an experimental sense of when np complete problems become unmanageable (and what conditions make the problem simpler... like traveling salesman problem is more manageable in 2D euclidean distance than in general)

[@detectivegenius9744]

damn! very helpful video

[@RiskByNumbers]

My first ever "damn!" response received for any form of educational content. How awesome -- it made my day! Thank you so much, and thanks for the interest in the channel, @detectivegenius9744.

[@adityanayak20]

Make more mathematical videos like this. Ur animations are damm great and if possible make an advance statistics playlists with such animations.

[@RiskByNumbers]

Thanks, @adityanayak20. Really appreciate the kind note! Looking forward to when this channel is large enough to have many playlists.

[@davidclercrodriguez5801]

what's the formula to calculate the 256?

[@michelgordillo8797]

it seems to be the sum of the nodes times the choices per node, per stage, Σ N * C = (4x1 + 4x4 +4x4 +4x4 + 4x1).

[@RiskByNumbers]

David: Fantastic question and, in retrospect, something that I should have expanded on in the video. It looks like I cannot paste an image into the comment, so I'll try as best I can to answer this question with text. Let's index each location for each stage as 1-4 in ascending order. At the end of each stage, let's list all possible directions we could have gone, and the total number I'll note in parentheses. I'll fully list out all combinations for the first 3 stages, and then simply write the total for each subsequent stage. Stage 1 (1): 1 Stage 2 (4): 11, 12, 13, 14 Stage 3 (16): 111, 112, 113, 114, 121, 122, 123, 124, 131, 132, 133, 134, 141, 142, 143, 144 Stage 4 (64) Stage 5 (256) Stage 6 (256) In this problem, the number of permutations largely grows exponentially with the number of stages. In the last stage, we remain at 256, as in Stage 5 we only have 1 available action for each state (not 4), as we are going to our arrival location. I hope that makes sense. The key point: enumerating across all permutations can become quite large, quite quickly for problems with a number of states, actions, and stages. I akin dynamic programming to snipping branches. As we solve each stage, we "snip" the sub-optimal solutions from future calculations, allowing us to solve our problems much faster. The next video in this series will cover how we can solve a probabilistic financial problem through this technique. Thanks for your interest, and it seems that this message has gotten quite long -- academics are not known for their brevity!

[@GabrielaSosa-n9l]

@@RiskByNumbers Thank you! Can't wait for the next video.

[@RiskByNumbers]

Thanks, Gabriela, for the positive note!

[@KanaKanaXOR]

I implemented it: ``` def shortest_path_dp(routes: tuple[tuple[tuple[int]]]) -> list[int]: n, m = len(routes), len(max(routes, key=lambda x: len(x))) dp = [([0] * m) for _ in range(n + 1)] for i, stage in enumerate(reversed(routes)): idx = n - i - 1 last, cur = dp[idx + 1], dp[idx] for j in range(len(stage[0])): cur[j] = min(stage, key=lambda x: x[j] + last[j])[j] + last[j] return [min(zip(range(len(dp[i])), dp[i]), key=lambda x: x[1])[0] for i in range(1, len(dp) - 1)] def main(): routes = ( ((12,), (16,), (12,), (14,)), ((14, 14, 12, 19), (19, 20, 13, 10), (10, 17, 15, 11), (13, 16, 14, 14)), ((14, 12, 13, 18), (18, 19, 10, 12), (16, 15, 11, 13), (15, 16, 16, 14)), ((16, 10, 18, 16), (15, 13, 12, 14), (16, 10, 13, 12), (20, 14, 10, 11)), ((10, 12, 15, 13),), ) path = shortest_path_dp(routes) print(path) if __name__ == '__main__': main() ``` I used to think of them as (recursion + caching). The way you explained this, you can apply this for solving games like TicTacToe. Each stage will be then moves by players (the stages will alternate between player 1 and 2).

[@RiskByNumbers]

Very cool, @anikanapy6545, to have folks like you sharing their implementation with others! With regards to TicTacToe, my goal is to introduce a bit of reinforcement learning (RL) in this mini-series, where we can see the connection between dynamic programming and RL in learning optimal policies. TitTacToe may be a nice problem to show that connection!