Body: <p>I am self-teaching reinforcement learning and for now I am trying to solve the following DP problem:</p>
  <blockquote>
  <p>A driver is looking for inexpensive parking on the way to his destination. The parking
  area contains <span class="math-container">$N$</span> spaces, and a garage at the end. The driver starts at space 0 and
  traverses the parking spaces sequentially, i.e., from space <span class="math-container">$k$</span> he goes next to space <span class="math-container">$k + 1$</span>,
  etc. Each parking space <span class="math-container">$k$</span> costs <span class="math-container">$c(k)$</span> and is free with probability <span class="math-container">$p(k)$</span> independently
  of whether other parking spaces are free or not. If the driver reaches the last parking
  space <span class="math-container">$N − 1$</span> and does not park there, he must park at the garage, which costs <span class="math-container">$C$</span>. The
  driver can observe whether a parking space is free only when he reaches it, and then, if
  it is free, he makes a decision to park in that space or not to park and check the next
  space. The problem is to find the minimum expected cost parking policy.</p>
  </blockquote>
  <p>As a first step, I defined the state space at stage <span class="math-container">$i$</span> to be <span class="math-container">$S_i = \{1, ...,\min\{i, N\}\}$</span> (because <span class="math-container">$\min\{i, N\}$</span> is the farthest that the driver can reach), and the action space to be <span class="math-container">$A_i = \{0, 1\}$</span>, where <span class="math-container">$0$</span> stands for the action of staying at the current space, and <span class="math-container">$1$</span> denotes moving on to the next space.</p>
  <p>How am I supposed to define the state-reward distribution? At stage <span class="math-container">$i$</span>, is it that
  <span class="math-container">$$
  \begin{cases}
  p_i(s+1, c(s+1)\mid s, 1) = p(s+1)\\
  p_i(s, c(s)\mid s, 0) = p(s)
  \end{cases}\;(s &lt; N),\quad p_i(s, C\mid s, 0) = 1\quad (s = N)?
  $$</span></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-26T17:57:22.283Z
Comments.Text: https://dspace.mit.edu/bitstream/handle/1721.1/75813/6-231-fall-2008/contents/exams/midterm_solution.pdf ?
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-26T18:30:50.040Z
Comments.Text: Would you add your current idea of state and policy? You mentioned state of parking space. How about state of driver?
Comments.UserDisplayName: Cloud Cho
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-26T21:38:13.227Z
Comments.Text: @CloudCho Oh I first wanted to define the driver's state via his location - but I ignored that his target was to park the car instead of reaching a certain parking space...
Comments.UserDisplayName: ArGenya
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-26T21:45:38.553Z
Comments.Text: If the driver rewarded by parking his car in a parking spot. Is his goal the max rewarding parking spot (cheapest one) or park, pull out and park in different spots to increase rewards?
Comments.UserDisplayName: Cloud Cho
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-26T22:02:16.677Z
Comments.Text: @CloudCho The driver simply stops at where he decides to park.
Comments.UserDisplayName: ArGenya
Tags: <reinforcement-learning><dynamic-programming>
Title: Clarification on Formulation of a DP Problem
UserDisplayName: ArGenya
ThreadText: # Clarification on Formulation of a DP Problem
  
  (Asked by: username_0 on 2023-09-26)
  
  I am self-teaching reinforcement learning and for now I am trying to solve the following DP problem:
  
  > A driver is looking for inexpensive parking on the way to his destination. The parking
  > area contains $N$ spaces, and a garage at the end. The driver starts at space 0 and
  > traverses the parking spaces sequentially, i.e., from space $k$ he goes next to space $k + 1$,
  > etc. Each parking space $k$ costs $c(k)$ and is free with probability $p(k)$ independently
  > of whether other parking spaces are free or not. If the driver reaches the last parking
  > space $N − 1$ and does not park there, he must park at the garage, which costs $C$. The
  > driver can observe whether a parking space is free only when he reaches it, and then, if
  > it is free, he makes a decision to park in that space or not to park and check the next
  > space. The problem is to find the minimum expected cost parking policy.
  
  As a first step, I defined the state space at stage $i$ to be $S\_i = \{1, ...,\min\{i, N\}\}$ (because $\min\{i, N\}$ is the farthest that the driver can reach), and the action space to be $A\_i = \{0, 1\}$, where $0$ stands for the action of staying at the current space, and $1$ denotes moving on to the next space.
  
  How am I supposed to define the state-reward distribution? At stage $i$, is it that
  $$
  \begin{cases}
  p\_i(s+1, c(s+1)\mid s, 1) = p(s+1)\\
  p\_i(s, c(s)\mid s, 0) = p(s)
  \end{cases}\;(s < N),\quad p\_i(s, C\mid s, 0) = 1\quad (s = N)?
  $$
  
  **Tags:** reinforcement-learning, dynamic-programming
  
  > **Comments:**
  > **username_1**: https://dspace.mit.edu/bitstream/handle/1721.1/75813/6-231-fall-2008/contents/exams/midterm_solution.pdf ?  
  > **username_2**: Would you add your current idea of state and policy? You mentioned state of parking space. How about state of driver?  
  > **username_0**: @username_2 Oh I first wanted to define the driver's state via his location - but I ignored that his target was to park the car instead of reaching a certain parking space...  
  > **username_2**: If the driver rewarded by parking his car in a parking spot. Is his goal the max rewarding parking spot (cheapest one) or park, pull out and park in different spots to increase rewards?  
  > **username_0**: @username_2 The driver simply stops at where he decides to park.  
  
  ---
  
  ## 0 answers
  
  