Body: <p>I am trying to solve a dynamic programming toy example. Here is the prompt: imagine you arrive in a new city for <span class="math-container">$N$</span> days and every night need to pick a restaurant to get dinner at. The qualities of the restaurants are iid according to distribution <span class="math-container">$F$</span> (assume [0,1]). The goal is to maximize the sum of the qualities of the restaurants that you get dinner at over the <span class="math-container">$N$</span> days. Every day you need to choose whether you go to a new restaurant and obtain a utility drawn at random from distribution <span class="math-container">$F$</span>, or you go to the best restaurant you have attended so far, and obtain a known utility.</p>
  <p>Here is my formulation:</p>
  <ul>
  <li>Let <span class="math-container">$m_t$</span>, the state at time <span class="math-container">$t$</span>, denote the quality of the best restaurant visited so far.</li>
  <li>Let <span class="math-container">$a_t \in \{Q, E\}$</span> be the action at time <span class="math-container">$t$</span>; <span class="math-container">$E$</span> for EXPLORE, <span class="math-container">$Q$</span> for quit.</li>
  <li>Given the action set, the rewards are (<span class="math-container">$W_t$</span> denotes the random variable of the quality of the restaurant drawn at random at time <span class="math-container">$t$</span>):
  <span class="math-container">$$r_t(m_t | E) = W_t \sim F $$</span>
  <span class="math-container">$$r_t(m_t | Q) = m_t  $$</span></li>
  <li>The transition probabilities at time <span class="math-container">$t$</span> are:
  <span class="math-container">$$ p_t\big (  m_t |  m_t, Q \big ) =1 $$</span>
  <span class="math-container">$$ p_t\big (  m_t |  m_t, E \big ) =F(m_t), \text{ with } W_{t} \in [0, m_t]$$</span>
  <span class="math-container">$$ p_t\big (  W_t |  m_t, E \big ) =1-F(m_t), \text{ with } W_{t} \in ( m_t, 1]  $$</span></li>
  </ul>
  <p>First I write down the Bellman optimality equations:
  For <span class="math-container">$t=N$</span>, I get:
  <span class="math-container">$$ u^*_N (m_N) = \max_{a_t \in \{Q, E\}} \big\{ m_N, \ \  E(W_N) \big\}  $$</span>
  For <span class="math-container">$t&lt;N$</span>, I get:
  <span class="math-container">$$
   u^*_t (m_t) = 
   \max_{a_t \in \{Q, E\}}  \bigg\{ m_t+ u^*_{t+1} (m_t) , \ \ \ E(W_t)+  u^*_{t+1} (m_t) F(m_t) + \int_{m_t}^1 u^*_{t+1} (x) dF(x) \bigg\}  
  $$</span></p>
  <p>What I am trying to show is that, if it is optimal to quit exploration in period <span class="math-container">$\tau$</span>, then it is optimal to not explore in every period <span class="math-container">$t=\tau+1, ..., N$</span>. In agreement with the equations above, I assume:
  <span class="math-container">$$m_\tau- E(W_\tau) \geq   \int_{m_\tau}^1 (u^*_{\tau+1} (x)-u^*_{\tau+1} (m_\tau))  dF(x) $$</span>
  and I want to show:
  <span class="math-container">$$m_\tau - E(W_{\tau+1}) = m_\tau - E(W_{\tau})\geq   \int_{m_\tau}^1 (u^*_{\tau+2} (x)-u^*_{\tau+2} (m_t))  dF(x) $$</span></p>
  <p>I have been reading the structured policies chapters on Puterman and Bertsekas (Vol II) and did not find anything that could get me rolling. Any help or pointer to literature is more than welcome!</p>
  <p>After I show this I can argue that there will exist a sequence of thresholds <span class="math-container">$c_t$</span> so that is is optimum to stop exploration at time <span class="math-container">$t$</span> it <span class="math-container">$m_t \geq c_t$</span>.</p>
  <p><strong>EDIT</strong>: Distribution <span class="math-container">$F$</span> is known to the tourist.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-22T06:54:01.650Z
Comments.Text: I think you need to declare whether the agent knows $F$. Knowing $F$ allows the agent to make decisions about optimality differently from if they don't know $F$.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-22T20:10:28.700Z
Comments.Text: Distribution $F$ is know. I added that in the question.
Comments.UserDisplayName: learningowl
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-30T04:57:04.710Z
Comments.Text: To clarify what your question really is, can you put it in the title of your post? "Structured policies in dynamic programming" is not really a question. I also don't see any question in the body of your post.
Comments.UserDisplayName: nbro
Tags: <optimization><dynamic-programming>
Title: Structured policies in dynamic programming: solving a toy example
UserDisplayName: learningowl
ThreadText: # Structured policies in dynamic programming: solving a toy example
  
  (Asked by: username_0 on 2022-04-21)
  
  I am trying to solve a dynamic programming toy example. Here is the prompt: imagine you arrive in a new city for $N$ days and every night need to pick a restaurant to get dinner at. The qualities of the restaurants are iid according to distribution $F$ (assume [0,1]). The goal is to maximize the sum of the qualities of the restaurants that you get dinner at over the $N$ days. Every day you need to choose whether you go to a new restaurant and obtain a utility drawn at random from distribution $F$, or you go to the best restaurant you have attended so far, and obtain a known utility.
  
  Here is my formulation:
  
  * Let $m\_t$, the state at time $t$, denote the quality of the best restaurant visited so far.
  * Let $a\_t \in \{Q, E\}$ be the action at time $t$; $E$ for EXPLORE, $Q$ for quit.
  * Given the action set, the rewards are ($W\_t$ denotes the random variable of the quality of the restaurant drawn at random at time $t$):
    $$r\_t(m\_t | E) = W\_t \sim F $$
    $$r\_t(m\_t | Q) = m\_t $$
  * The transition probabilities at time $t$ are:
    $$ p\_t\big ( m\_t | m\_t, Q \big ) =1 $$
    $$ p\_t\big ( m\_t | m\_t, E \big ) =F(m\_t), \text{ with } W\_{t} \in [0, m\_t]$$
    $$ p\_t\big ( W\_t | m\_t, E \big ) =1-F(m\_t), \text{ with } W\_{t} \in ( m\_t, 1] $$
  
  First I write down the Bellman optimality equations:
  For $t=N$, I get:
  $$ u^\*\_N (m\_N) = \max\_{a\_t \in \{Q, E\}} \big\{ m\_N, \ \ E(W\_N) \big\} $$
  For $t<N$, I get:
  $$
  u^\*\_t (m\_t) =
  \max\_{a\_t \in \{Q, E\}} \bigg\{ m\_t+ u^\*\_{t+1} (m\_t) , \ \ \ E(W\_t)+ u^\*\_{t+1} (m\_t) F(m\_t) + \int\_{m\_t}^1 u^\*\_{t+1} (x) dF(x) \bigg\}
  $$
  
  What I am trying to show is that, if it is optimal to quit exploration in period $\tau$, then it is optimal to not explore in every period $t=\tau+1, ..., N$. In agreement with the equations above, I assume:
  $$m\_\tau- E(W\_\tau) \geq \int\_{m\_\tau}^1 (u^\*\_{\tau+1} (x)-u^\*\_{\tau+1} (m\_\tau)) dF(x) $$
  and I want to show:
  $$m\_\tau - E(W\_{\tau+1}) = m\_\tau - E(W\_{\tau})\geq \int\_{m\_\tau}^1 (u^\*\_{\tau+2} (x)-u^\*\_{\tau+2} (m\_t)) dF(x) $$
  
  I have been reading the structured policies chapters on Puterman and Bertsekas (Vol II) and did not find anything that could get me rolling. Any help or pointer to literature is more than welcome!
  
  After I show this I can argue that there will exist a sequence of thresholds $c\_t$ so that is is optimum to stop exploration at time $t$ it $m\_t \geq c\_t$.
  
  **EDIT**: Distribution $F$ is known to the tourist.
  
  **Tags:** optimization, dynamic-programming
  
  > **Comments:**
  > **username_1**: I think you need to declare whether the agent knows $F$. Knowing $F$ allows the agent to make decisions about optimality differently from if they don't know $F$.  
  > **username_0**: Distribution $F$ is know. I added that in the question.  
  > **username_2**: To clarify what your question really is, can you put it in the title of your post? "Structured policies in dynamic programming" is not really a question. I also don't see any question in the body of your post.  
  
  ---
  
  ## 0 answers
  
  