Thanks for the references; I’ll need some time to review them. In the meanwhile, I’ll make some quick responses.
As a side note, I’m not sure how tree search comes into play; in what way does tree search require unbounded steps that doesn’t apply equally to linear search?
I intended tree search as just one example, since minimax tree search is a common example for game-based RL research.
No finite agent, recursive or otherwise, can plan over an unbounded number of steps in finite time...
In general, I agree. Though there are notable exceptions for cases such as (not mutually exclusive):
a closed form solution is found (for example, where a time-based simulation can calculate some quantity at an any arbitrary time step using the same amount of computation)
approximate solutions using a fixed number of computation steps are viable
a greedy algorithm can select the immediate next action that is equivalent to following a longer-term planning algorithm
… so it’s not immediately clear to me how iteration/recursion is fundamentally different in practice.
Yes, like I said above, I agree in general and see your point.
As I’m confident we both know, some algorithms can be written more compactly when recursion/iteration are available. I don’t know how much computation theory touches on this; i.e. what classes of problems this applies to and why. I would make an intuitive guess that it is conceptually related to my point earlier about closed-form solutions.
Thanks for the references; I’ll need some time to review them. In the meanwhile, I’ll make some quick responses.
I intended tree search as just one example, since minimax tree search is a common example for game-based RL research.
In general, I agree. Though there are notable exceptions for cases such as (not mutually exclusive):
a closed form solution is found (for example, where a time-based simulation can calculate some quantity at an any arbitrary time step using the same amount of computation)
approximate solutions using a fixed number of computation steps are viable
a greedy algorithm can select the immediate next action that is equivalent to following a longer-term planning algorithm
Yes, like I said above, I agree in general and see your point.
As I’m confident we both know, some algorithms can be written more compactly when recursion/iteration are available. I don’t know how much computation theory touches on this; i.e. what classes of problems this applies to and why. I would make an intuitive guess that it is conceptually related to my point earlier about closed-form solutions.
Totally, good point!