Multi-Objective Reinforcement Learning for Forward-Backward Markov Decision Processes

“example illustrating FBMDP strengthen the motivation. algorithm may be computationally expensive”

We have included an example in the context of computation offloading in the revised submission to motivate the applicability of FB-MDPs to a different scenario. Computational complexity is determined by two factors: the selection of the learning rate and the episodic MCS-average mechanism. The former is not a concern, as the simulations suggest that even a fixed learning rate obtains convergence. The latter is primarily affected by the number $N_{MCS}$ of critic agents that should be implemented. Based on simulations, 3 or 4 are sufficient to reach convergence. As a consequence, the complexity of FB-MOAC is competitive with respect to a forward-only RL algorithm.

“How do forward and backward processes conflict”

The forward and backward dynamics compete with each other as they depend on the action variables and they correspond to action-dependent rewards. Specifically, the optimal action from the perspective of forward rewards [Eqs. (20) and (21)] are not necessarily aligned with the optimal action from the perspective of backward reward [Eq. (22)]. This has been numerically evaluated by the ablation study in Section 4.2.3 of the revised manuscript. In particular, Figure 2 shows that merely optimizing the forward rewards causes the backward reward to diverge.

“Can’t it be analyzed by a forward MDP with an absorbing state”

The backward dynamics starts from a known state, however, it moves backwards over time: the current state depends on the future state and action, in contrast with the forward dynamics. Note that converting the backward dynamics by flipping the time does not solve the issue as the resulting state would now depend on the actions that happen in a far future. Hence, it cannot actually be formulated according to a forward-MDP with absorbing states.

“The analysis does not reflect that conflict of trajectories”

We appreciate this remark. Lemma 3.1 differs from its counterpart for the forward dynamics as: it depends on the backward reward; the transition trajectory and the backward value function in Eq. (7) are obtained based on a policy distribution that only depends on the forward state. Hence, they are in conflict since the rewards compete, resulting in several challenges: jointly optimizing the action-coupled backward and forward rewards; devising a multi-objective algorithm that updates the policy after the forward and backward dynamics are evaluated; and the convergence analysis for the devised multi-objective actor agent, shared between the forward and backward dynamics.

“why is γ ∈(0,1] ?”

In typical problems, setting $\gamma=1$ generally suffices. In our case, however, we observed that the backward reward diverges for $\gamma>0.97$ and the sample-efficiency of the algorithm remarkably worsens for $\gamma<0.9$.

“why is the \pi(.) conditioned on s_t and not on y_t”

The backward state moves backwards over time and is not known in advance. The strategy $\pi(. | s_t)$ simplifies the algorithm derivation. Moreover, it does not constrain solution optimality since it is updated after both the forward and backward procedures are evaluated, and it drives the backward state to optimally evolve based on this optimal policy. Hence, both the backward and forward rewards are jointly optimized. Note that a policy equal to $\pi(.| s_t, y_t)$ does not allow writing the Bellman equation for the backward dynamics, and the expression of the backward reward is complex, as indicated in Lemma 3.1 of the revised manuscript.

“The computation of β_f∗ and β_b∗ needs to be done”

The analysis in Theorem C.1 provides the conditions that guarantee convergence. In practice, one could choose simple learning-rate settings with a confidence threshold such that these conditions are satisfied during the execution of the algorithm.

“Can’t equation (18) be expressed as a forward MDP?”

Thanks for the valuable comment. It is not possible to appropriately convert this controlled backward dynamics to a standard forward one. Specifically, if we flip the time-slot for the backward state we end up with a forward state which depends on the future actions that have not occurred yet and will happen in the far future. Hence, the states cannot be obtained by traversing onward over time.

“Enhancement of presentation … challenges in obtaining the analytical results?”

We have improved the presentation in the revised submission. Our work entails solving several challenges related to the analysis. First, we had to derive a backward version of the Bellman equations by identifying an action-coupled class of FB-MDPs. Second, we devised a shared entity for the actor agent which is updated based on the forward and backward stochastic rewards. To prove its convergence, we proposed a novel approach called episodic MCS-average. Finally, we analyzed convergence for merely smooth (and not convex) objective functions.

“The paper is not easy to follow. There are many notational errors in the core formula”

Thanks for the valuable feedback. We carefully reviewed the notation and fixed some inconsistencies in the revised manuscript.

“There are no baseline algorithms to compare”

We agree that the random approach is not enough for comparison. Therefore, we have included two additional schemes for comparison purposes:Least Frequently Used (LFU), a rule-based approach widely used in the literature on caching; and F-MDP, a learning-based algorithm that replaces the backward MDP with the forward-only formulation.

“When can we consider this backward dynamics setting?”

The need for FB-MDPs depends on the problem environment under consideration. We have included an example in the context of computation offloading in the revised submission to motivate the applicability of FB-MDPs to a different scenario. Specifically, mobile devices offload computationally intensive tasks to an edge server, which processes them according to its computational capacity. The edge server has a buffer to store the tasks that cannot be immediately processed, which happens when there is no spare computational capacity. The new example has been mentioned in the introduction and detailed in the appendix.

“Providing high-level pictures describing the environment is recommended”

Thank you for your insightful comment. The hybrid experiment considered a heterogeneous network with two different node tiers: Base-stations (BSs) and helper-nodes (HNs). There exists a set of users that request files from a database containing $N$ different files. These files are requested based on a time-varying file popularity distribution. The network serves the users with a hybrid content-delivery scheme by employing both BSs and HNs. BSs are connected to the core-network and HNs are equipped with caches to proactively store files. The hybrid scheme is based on multicast transmissions from HNs and unicast transmissions from BSs. The HNs cache most popular files and cooperatively transmit the cached files across the network. Conversely, the BSs individually serve the users that request files. To do so, the BS first fetches the file from the core network and then sends it to the user. Transmissions are repeated until the data are successfully received by the user. Considering the popularity of content and the outage probability, a forward dynamics is found for the request probability which is expressed in Eq. (18). As an important metric for the transmission schemes, we consider the expected latency for successful content reception. Due to the outage possibility, a backward dynamics is extracted for the expected latency presented in Eq. (19). Then, based on the content popularity and expected latency, we are considering three conventional metrics to optimize the network performance. These metrics are as follows. A quality-of-service metric that indicates how much the users are satisfied, the bandwidth consumption that measures the required bandwidth of the whole network and the overall expected latency that shows the latency for all file requests.

“provide anonymous source code”

This is indeed an interesting point. We are reviewing and improving the clarity of the code used for the paper and are committed to anonymously publish it by the end of the discussion phase.

“Lemma 1 does not tell about which Pareto-optimal point it converges”

Thank you for the precise remark. Indeed, this Lemma does not specify which Pareto-optimal solution the devised algorithm converges to. However, the algorithm is guaranteed to converge to one of the Pareto-optimal points. As for our proposed method, we have proved convergence for both cases of strongly-convex and Lipschitz-smooth objectives and shown that all the forward and backward expected losses monotonically decrease as the iteration increases (Theorem C.1). A conventional approach for the multi-objective problems is scalarization, namely, by first constructing a scalar reward and then applying a single-objective algorithm. However, this approach makes the solution highly dependent on the selected scalarization technique. Instead, our approach aims to learn a scale-independent multi-objective learning approach. Furthermore, the considered methodology enables us to analyze the convergence of the proposed algorithm.

“Conditions of Corollary 1 should be stated more precisely.”

We have modified this Corollary to more precisely express these conditions, according to the comment.

“Does saving past model parameters raise any memory issues of the algorithm?”

The FB-MOAC algorithm does not rely on storing the whole history of the model parameters: only the previous parameter is needed for the purpose of policy update. Our implementation ran on a laptop and did not experience any memory-related issues during numerical simulations.

“forward-backward MDP could be further justified”

We have included an example in the context of computation offloading in the revised submission to motivate the applicability of FB-MDPs to a different scenario. Specifically, mobile devices offload computationally intensive tasks to an edge server, which processes them according to its computational capacity. The edge server has a buffer to store the tasks that cannot be immediately processed, which happens when there is no spare computational capacity. The new example has been mentioned in the introduction and detailed in the appendix.

“Lemma 3.1 suggests a first-order iterative descent”

We appreciate the remark and the opportunity to clarify. The convergence of optimization algorithms based on this Lemma can be proven under the assumption of Lipschitz-smooth functions (Fliege et al., 2019)*. Our paper proves that for two cases: convexity and smoothness alone. Specifically, a locally Pareto-optimal solution with a convergence rate of $O(1/\sqrt{K})$ for the Lipschitz-smooth case is guaranteed, where $K$ is the number of updates. Section 4.1 provides a concise summary of these results, whereas Appendix C details the related derivation.

• J. Fliege, A. I. F. Vaz & L. N. Vicente. “Complexity of gradient descent for multiobjective optimization,” Optimization Methods and Software, 34:5, 949-959, 2019.

“Bellman optimality equations offer a salient characterization”

The Bellman optimality equation characterizes the solution of dynamic programming algorithms and our work targets RL algorithms for action-coupled FB-MDPs. However, we here derive an alternative equation for FB-MDPs, namely, the Bellman Pareto-optimality equation. Please refer to the Lemma 3.1 of the revised manuscript and the following Remark.

“the class of stationary policies is large enough to contain an optimal policy”

We consider the forward and backward transition probabilities as stationary. We also assume that the forward and backward rewards are only coupled within the action space. Hence, the forward and backward value functions are stationary. Therefore, designing an optimal policy does not need to consider the time or the previous history of forward states. The same also holds for the backward reward. The evolution of the backward state is optimally determined by the forward state throughout the action space. As a result, a non-stationary policy distribution is not beneficial to jointly optimize the forward and backward rewards.

“forward MDP formulation could still be used to solve this problem”

Thanks for your suggestion. The backward reward is a part of the environment in the considered experiment. Therefore, replacing only that with another one would lead to a sub-optimal policy. In line with your suggestion, we consider an additional formulation to replace the backward dynamics. For this, we utilize this fact that minimizing both the outage probability and time-slot duration result in minimizing the overall latency, based on Eq.(19). Please refer to the revised manuscript for the additional results of the new formulation.

“_ experimental results are not strong _”

We point out that the experiments already considered two different cases: a hybrid and a multicast scheme. They differ from each other in terms of the system model, action parameters, reward function, and MDPs. Moreover, we do agree that the random approach is not a compelling baseline. Hence, we have included two additional schemes for comparison purposes: Least Frequently Used (LFU), a rule-based approach widely used in the literature on caching; and F-MDP, a learning-based algorithm that replaces the backward MDP with the forward-only formulation mentioned above.

“In Eq.(18), shall the 1/2 in the second term be just 1”

Thanks for the precise comment. The 1/2 factor is used under the assumption that requests in a time-slot are submitted according to a uniform distribution, corresponding to completely uncoordinated operations among users.

“How to define the event of multicast outage?”

The multicast outage happens when a user cannot successfully receive the requested file because the received signal quality is too low. The probability that such an outage occurs is given by $\mbox{Pr} ( B \log_2(1+\gamma)< R )$, where $\gamma$ is the Signal-to-Noise Ratio associated with the user, $B$ the bandwidth associated with the multicast scheme, and $R$ the desired transmission rate.

“how to derive the probability”

A closed-form expression of the probability has been obtained in (Amidzadeh et al., 2022). The derivation relies on leveraging stochastic geometry under the assumption that the base-stations are distributed according to a Poisson process.

“How does the “request process” of each user work?”

The users send requests to retrieve files towards the BSs by uplink transmissions. Each BS is responsible to deliver the file to the users associated with it and by using the conventional unicast scheme.