0
$\begingroup$

Suppose there is a dynamic program that the state of the problem grows over time (more info is added to the state of the problem over time) and at each time, we need all historical data, full history, or all information gathered in a time window. My first question is if this model can be considered a Markov decision process? In an MDP, the state of the current time should be based on the state of the problem in the former time period. Here, this is true but we have gathered all information.

My second question is what are the general approaches to solve history-dependent dynamic programs? If we summarize information as a probability distribution, we would lose the exact information and our results will be suboptimal. I would be thankful if you can share some references for discrete and continuous-time problems.

Note: I asked this question in the following group, but I don't know if it is possible to transfer the question to this group or not. This link

$\endgroup$
5
  • $\begingroup$ Concerning 2) You state that results will be suboptimal if summarizing (i.e. extracting) information. Does that mean that you are looking for an exact method? $\endgroup$
    – PeterD
    Jun 19 at 20:12
  • $\begingroup$ Not an exact solution, but I am willing to solve it with an error bound. I am wondering if I store all historical data as a probability distribution, is the problem transformed to a POMDP? For example, instead of storing all customers' age, I use a probability distribution that matches the data. $\endgroup$
    – Amin
    Jun 20 at 2:44
  • $\begingroup$ Even though Markov can be considered a loose statement it usually indicates "memorylessness" (no info beyond the current state). Also if you are thinking of dynamic programming in LP or MIP context you will be handling decision variables at all stages. Therefore you will be using all history with something that can be called "markovian" (perhaps). Can you provide a minimal application example rather than a general statement? $\endgroup$
    – berkorbay
    Jun 20 at 8:43
  • $\begingroup$ Suppose we have perishable products in the inventory and also some lead times for orders. In this case, we need to store the lifetime of products and also former orders. $\endgroup$
    – Amin
    Jun 25 at 18:46
  • $\begingroup$ Can't you describe that without the full information of those orders? So lets say you have one product: Then you can have in your state the amount of goods that perishes in 1 day, the amount that perishes in 2 days (lets say up to n days) etc. And for ordered goods the same: The amount that will arrive in 1 day, 2 days ..... Of course that will be quite large so you might use e.g. approximate dynamic programming (ADP) to solve it. $\endgroup$
    – PeterD
    2 days ago

1 Answer 1

1
$\begingroup$

Apart from some "current" values, a state of the state machine can include the history of the previous state changes. Say the state consists of the two booleans, current state and previous state. You can have a function that takes such a state and returns another, also two booleans. One is the new "actual state" and another is the previous "actual state".

You can then apply all approaches created for the function that takes an integer (0..3 in our case) and returns a similar integer: x <- f(x), simple as that. Having longer history would just mean a larger integer that remains countable.

$\endgroup$
1
  • $\begingroup$ Thanks for your response. Could you please give an example? It is not clear how to handle it. Thanks $\endgroup$
    – Amin
    Jun 20 at 2:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.