# Methods for sequential decision optimization problem with nonlinear bayesian reward function

I am attempting to grasp if there are any other methods out there that i am not aware of that can be beneficial given my problem context. Being inspired from optimal experimental design communities and RL-communities i have a sense there is.

To illustrate the problem at hand, consider a multivariate Bayesian regression model represented as $$\hat{y}_t = b_{1, t} \cdot x_{1,t}^{c_1} + b_{2, t} \cdot x_{2,t}^{c_2}$$ where as $$\hat{y}_t$$ denotes predicted values and $$y_t$$ observations. The purpose of this model is to estimate rewards $$\hat{y}_t$$ based on inputs ($$x_{1,t}$$, $$x_{2,t}$$) at each time step denoted by $$t$$. The parameters $$b_{1, t}$$ and $$b_{2, t}$$ are time-variant implying that they may vary over the horizon and are not constant. For instance, we could consider day of the week dummies where day-of-the-week parameter has a gaussian prior or e.g a Gaussian random walk prior that associates with the day of the month, allowing it to capture and generalize the day-of-the-month effect observed across multiple months (assume we have daily historical data). $$c_1$$ and $$c_2$$ follow a gamma distribution. Lets assume a normally distributed likelihood $$L(y_t|b_1, b_2, c_1, c_2, x_{1, t}, x_{2, t}) \sim \mathcal{N}(\hat{y_t}, \sigma^2)$$. I aim to plan inputs over a given horizon $$H$$ given a specified budget $$\left(\sum_{t \in H} x_{1,t} + x_{2,t} \le \mbox{budget}\right)$$, with the main objective of maximizing cumulative rewards. To help with this goal, it is important to also gain knowledge about the model parameters to facilitate improved allocation of inputs for maximizing cumulative rewards in the future.

Note that every day, we have the ability to adjust our planning in accordance with the newly acquired information. As a result, we can recompute our decisions daily and implement them, essentially enabling us to recompute our decisions "online". Also note that we have a lot of time to recompute our (batch)decisions every timestep.

I am aware of essentially two, maybe three different strategies of "solving" this problem. Consider the following algorithm showcasing these different strategies:

1. Estimate the posterior with e.g MCMC factoring in our current dataset
2. Sample from the posterior
• Strategy 1: Sample a single set of parameters from the posterior(thompson sampling)
• Strategy 2: Sample many samples from the posterior(SAA)
3. Construct a deterministic optimization problem over the whole horizon with the previously sampled parameters
• Strategy 1: Objective function being $$\sum_{t \in H}\hat{y}_t$$ with the single sample as parameters
• Strategy 2: Objective function being $$\sum_{t \in H}\frac{1}{M}\sum_M \hat{y}_t$$ where $$M$$ denotes the quantity of samples
4. Solve the determinstic optimization problem subject to the budget constraint
5. Set allocation for today
6. Retrieve reward

A concern regarding all of these approaches is the omission of consideration for how our decisions might influence our future belief states and, consequently, subsequent decisions. The proposed exploration techniques seems to me somewhat adhoc.

Question: Considering the context, are there any other methods beyond the ones I proposed in the algorithm that could be superior and that can be employed to address this problem? If so, how would I proceed with implementing them?

• that is a very long question. very detailed. Commented Jul 26, 2023 at 2:56
• @EngrStudent should i shorten it down?, it is a complex problem and i think my proposals of strategies and breaking down some of my research could be really beneficial also for other practitioners.
– paul
Commented Jul 26, 2023 at 6:59
• @paul I don't recall us ever having a maximum length for questions (someone correct me if I'm wrong - I'm not going to check the rules on this right now). If everything in the question is necessary, I don't think it should be shortened. People who don't know how to answer the question will probably realize that after the first paragraph or two, so you won't be wasting their time. Some questions are inherently more detailed than others, and length simply can't be avoided in those cases. Commented Jul 26, 2023 at 14:58
• Also @paul - very nice job with formatting this question correctly for AI Stack Exchange! It's clear that you looked at your previous question that I edited and you made the relevant changes here (e.g. explicitly stating the question, using horizontal lines to partition the question, using good notation). Nice work, and we hope to see more of your questions in the future! I will take a look at this question probably by next week and see if I can answer it. Commented Jul 26, 2023 at 15:00
• @DeepQZero thank you, let me know if i should change anything in this question. best regards
– paul
Commented Aug 14, 2023 at 18:28

One possible alternative approach is incorporating deep reinforcement learning (DRL) techniques. These techniques are sequential since they incorporate lookahead, and they are designed to attempt to reach an optimal solution. Moreover, a Bayesian viewpoint can be adopted through incorporating a belief state over the unknown parameters. This belief state transforms the original POMDP into a belief MDP (see second paragraph of page 2 of this paper) where the observations are now belief states (see the wiki for more formal details). The belief state is generally more informative than a simple observation of a POMDP, which should aid in training speed and stability.

These DRL methods are appealing for the posed problem setting since (i) many have off-the-shelf implementations for fast use, (ii) they natively navigate the exploration/exploitation dilemma, and (iii) they can be quickly applied to any new variant of the posed problem as long as it is modeled correctly (e.g. as a belief MDP). Since the question is asking about implementation details, this answer will detail the some aspects of the approach discussed in aforementioned paper. The first major consideration is the construction of the state for use in the neural network. Most practical DRL algorithms will optimize over a fixed planning horizon which we will assume is of length $$T$$. The first order of business is to create a one-hot encoding vector that indicates the current experiment number. This initial vector will be $$0$$ everywhere except in index $$k-1$$ during experiment number $$k$$ (starting from index $$0$$): $$[\underbrace{0, 0, 0, \ldots, 0, \underbrace{1}_{\mbox{index}\ k-1}, 0, \ldots, 0}_{T}].$$ This vector needs to be augmented with the designs of each experiment as follows: $$[\underbrace{x_{1, t_0}, x_{2, t_0}, x_{1, t_1}, x_{2, t_1},\ldots, x_{1, t_{k-2}}, x_{2, t_{k-2}}, x_{1, t_{k-1}}, x_{2, t_{k-1}}, 0, 0, \ldots, 0, 0}_{2T}].$$ All designs yet to be chosen can simply be set to 0. Finally, the history of observations needs to be augmented as well, with future observations set to 0: $$[\underbrace{y_0, y_1, y_2, \ldots, y_{k-2}, y_{k-1}, 0, \ldots, 0}_{T}].$$ This entire vector is a vector of length $$T+2T+T = 4T$$, which is definitely a reasonable input size for a neural network under a planning horizon of ~30 days. Note that the designs and observations are all that is necessary (along with the original prior distribution) to construct the belief state. Since the state vector includes these quantities as a subset, also known as the information set $$I_k = \{x_{1, t_0}, x_{2, t_0}, y_0, x_{1, t_1}, x_{2, t_1}, y_1, \ldots, x_{1, t_{k-1}}, x_{2, t_{k-1}}, y_{k-1}\},$$ then the belief state is indeed encoded in nonparametric form in the state vector. By not constructing the belief state explicitly, intermediate belief states do not require any additional computation, which generally is non-negligible (see page 10 near equation 26 in the aforementioned paper for other details and discussion of a nonparametric belief state).

Following the state construction of the belief MDP, the issue of action constraints needs to be addressed since there is a design budget in the posed problem. Some off-the-shelf DRL libraries allow for parametric or constrained action spaces that are dependent on the state. In this case, augmenting the state vector with the remaining budget may aid in training speed due to a more explicit state representation (as opposed to the neural network needing to learn budget remaining from the designs).

After the above primary considerations are decided, all that is left is to code the belief MDP as a RL environment and apply some DRL algorithms. Some of the references in the linked question can help provide insight regarding the application of DRL to such environments. The posed problem seems non-trivial, open-ended, and may require substantial experimentation; therefore, this answer will be inherently limited in scope. Here are some more major considerations that may aid during the experimental process:

• Reward: Some applications provide a reward solely for the information gain in the unknown parameters. If information gain should be incorporated into the reward function, check out the references in the link question for ideas.

• Recomputing decisions: Since the entire analysis can be recomputed each night, the algorithm can be rerun with a shortened state vector. The new belief state can be computed and used as the prior distribution in the new algorithm. A shorter time horizon is generally easier for DRL algorithms and could either confirm the future design choices of past algorithms or even improve upon them.

• Belief state: The belief state representation was nonparametric and somewhat primitive. A better belief state representation may aid in training efficiency (e.g. parameters of the posterior distribution, if they are available).

• POMDP solutions: Since a belief MDP is a special case of POMDPs, techniques that solve POMDPs might be good baselines. For instance, this paper shows how memory-based architectures provide strong baselines for solving POMDPs with DRL.

Good luck, and keep us posted with any success stories!

• @paul In the above answer, I gave an example how the priors/posteriors/belief states could be represented in non-parametric form. Are you more interested in an answer with belief states in parametric form? I have some time this week to provide more ideas if you would like to solve the problem in a different way than presented in the answer. Commented Nov 7, 2023 at 16:16
• @paul Are you still around here? Commented Nov 16, 2023 at 19:55