A Tale of Dynamic Programming (2022) | Hacker News Reader

A Tale of Dynamic Programming (2022)

iagoleal.com

91 pointsBrajeshwar12 comments

Thanks for the refreshing reminder. This was one of my favourite topic at school but ended never used it in professional environment. However , I will definitely review the theory. Banach spaces and fix theorem were kind useful definition/tool but I always struggled to understand practical applications.

Thanks for sharing the article

Agreed, very cool article.

> I always struggled to understand practical applications.

Me too...and specifically with non-smooth dynamical systems. I always felt some better knowledge or intuition on my part could lead to understanding the practical application.

It's one reason I left academia... wtf this is cool, but wtf is this useful for?

The closest practical application I can fathom in this theoretical realm is optimization. And welp, since that underlies all AI, that's pretty important. Oh and cryptography.

>Proof: It all follows from applying the Banach fixed point theorem to the Bellman operator.

I disagree. When people hate mathematicians, it's because of things like this.

Why? Because it doesn't follow exclusively from the things listed. It also follows from the fact that c, T, A are bounded by the problem definition. Variable names in math confer no meaning, you can choose any variable name, hence you could have chosen an optimization problem that has no unique solution, simply out of spite.

Now the counter to that is that the introduction covered the restrictions on c, A and T but why drop them in the proof?

Thanks! What a great read.

side note: refreshing to read non ai articles

> An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

So an optimal policy is an optimal policy. Got it.

You have n decisions to make - this is your policy. After you make one, if your remaining n-1 decisions also optimal, then you have optimal policy.

So, an optimal policy is basically one that does not put you into a suboptimal position?

You can say it this way. Other way to put is optimal policy makes optimal decisions on every step as if it knows the future. If you looking for shortest distance in a graph then at every vertex it picks the right step, even if the edge is longer than other available in the vertex, as if it knows the future. This is why you cannot just build an algo implementing the policy, you have to find it with dynamic programming.

There's got to be a better way of saying this. "A policy is good if it keeps being good after the first time you use it" is the gist that I'm getting, but that's way too simplistic to actually tell you any of the value of dynamic programming.

I was pretty sure the "dynamic" in "dynamic programming" was used as a synonym for "awesome" and had nothing to do with system dynamics.

[0]:

> ... 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.

[0] https://en.wikipedia.org/wiki/Dynamic_programming#History_of...

Reply on news.ycombinator.com