action space; at the $k$-th decision instant (i.e., after placing the $(k-1)$-st relay), $\mu_k$ provides the distance at which the next relay should be placed (provided that the line does not end before that point), given the system state which is a function of the locations of previously placed nodes. Thus, the decisions are made based on the locations of the relays placed earlier. The first decision instant is the start of the line, and the subsequent decision instants are the placement points of the relays. Let $\Pi$ denote the set (possibly uncountable) of all deployment policies. Let $\mathbb{E}_{\pi}$ denote the expectation under policy $\pi$.

### The Unconstrained Problem

We recall from (\[eqn:capacity\_multirelay\]) that for a fixed length $L$ of the line and a fixed $N$, $e^{\rho y_1}+\sum_{k=2}^{N+1}\frac{e^{\rho y_k}-e^{\rho y_{k-1}}}{1+e^{\rho y_1}+\cdots+e^{\rho y_{k-1}}×}$ has to be minimized in order to maximize $R^{opt}_{P_T}(y_1,y_2,\cdots,y_N)$. $e^{\rho y_1}+\sum_{k=2}^{N+1}\frac{e^{\rho y_k}-e^{\rho y_{k-1}}}{1+e^{\rho y_1}+\cdots+e^{\rho y_{k-1}}×}$ is basically a scaling factor which captures the effect of attenuation and relaying on the maximum possible SNR $\frac{P_T}{\sigma^2}$.

Let $\xi>0$ be the cost of placing a relay. We are interested in solving the following problem: $$\begin{aligned}
 \inf_{\pi\in \Pi } \mathbb{E}_{\pi} \left( \left(e^{\rho y_1}+
\sum_{k=2}^{N+1}\frac{e^{\rho y_k}-e^{\rho y_{k-1}}}{1+e^{\rho y_1}+
\cdots+e^{\rho y_{k-1}}×} \right)+\xi N \right)\label{eqn:unconstrained_mdp}\end{aligned}$$ 