Part of my problem need to solve an finite-horizon, discrete-time MDP where the distribution of the state in each slot is i.i.d. and do not depends on the action. Are there any simple policies that can obtain the optimal solution? What if we consider adding a total cost constraint? Thanks!
If the state distribution in each period is iid regardless of the decision taken, then any policy is optimal. This is probably not the answer you are looking for. In most MDP models, the decision you take affect the transition probabilities to future state. Perhaps you can give more details about your problem and then I can give an answer that is of more help.
Thank you Joachim! I focused on the resource constrained case, and the problem becomes more difficult. Consider a $T$-horizon MDP, where the states $X_t$ are i.i.d. over time. In each time-slot, I decide to {transmit, wait}. If I transmit at $t$, I will receive $X_t$ units of utility, and pay 1-unit of energy. But I have only $P$ units of energy ($P < T$). What will be the optimal policy (simple policy, which may be expressed by closed form, rather than calculating the cost-to-go function), or near-optimal policy? Thanks!
It is not i.i.d because the amount of energy left P is part of the state and your choice of action influences the value of P. If the domain of X_t is enumerable, then the problem can be solved using standard a dynamic programming solution in time |X_t|*P*T.
Thanks Hakan. Yes, one can viewed this problem from that perspctive.However, I am wondering if there are some simple policies that can achieve good performance when $T$ and $P$ go to infinity in proportion. I think the one using the average resource constraints should be asymptotic optimal (as $T$ and $P$ go to infinity), as in E. Altman, Asymptotic properties of constrained Markov decision processes, 1993. I am not sure whether there are some other policies that have even better convergence performance.
Also, this is in fact an optimal multiple stopping problem. Are you aware of any policies fo such a problem?
Unfortunately I have little experience working with other stopping problems than the basic one so I am a bit out of my comfort zone. But for your problem, with T and P proportionally going to infinity, perhaps you can do something with the quantile function of X. One solution could be to use a policy where you transmit when X>Q(1-P/T) where Q is the quantile function of X. Then you will in average consume P/T resources and the expected value is E(X|X>Q(1-P/T)). However, this is just quick guesswork. I have no idea if it is optimal.
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Probability
- Probability Theory