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!