Let S be a system whose state can be altered by performing actions. Each action has two possible outcomes, and each outcome brings to a specific system state. A state is never visited two times, i.e., the state graph is a DAG (a tree, more specifically, where the root corresponds to the initial system state and each edge corresponds to an action). The probability of obtaining either one of the outcomes is known.

Notice that just B actions can be performed, and the pool of actions contains N different actions.

My objective is to devise an online optimal algorithm which identifies the best path to be taken, i.e., the path which guarantees the minimum cost. With the term "online" I am referencing to the following behavior:

  1. An action is chosen
  2. The system state is consequently modified
  3. A new action is chosen (taking into account the system state modification performed ad 2.)
  4. The system state is again modified according to the selected action
  5. ...

My first idea was the one of using A* in the following way:

  1. I ask A* to find the best sequence S of B actions to be performed
  2. I perform just the first action contained in S, and I modify the system state consequently (according to the outcome of the action)
  3. I ask A* to find the best sequence S' of (B-1) actions to be performed
  4. I perform just the first action contained in S' and I modify the system state consequently

The problem is that I don't know whether this solution is optimal (I didn't succeed in finding an optimality proof), and an optimal solution would be required in my case.

May you suggest another online algorithm (or, alternatively, a way of proving the optimality of the method I propose) to find an optimal solution for the problem?

EDIT: maybe something from game theory can be used instead (extensive form games with imperfect information). I am the player I that chooses the actions, while the player II is a dummy player that chooses the action "first-outcome" or "second-outcome", where "first-outcome" and "second-outcome" are my actions' possible outcomes.

NOTE: I posted a similar question here, although in my previous question an offline version was required, i.e., the modifications of the actions were not taken into account at each iteration.

Thanks in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.