Structured Reinforcement Learning for Incentivized Stochastic Covert Optimization

The oracle evaluates the gradient of the function $f$. The following is assumed about the oracle and the function $f$,

1. O1:

   Function $f:\mathbb{R}^{d}\to\mathbb{R}$ is continously differentiable and is lower bounded by $f^{*}$. Function $f$ is $\gamma$-Lipschitz continuous, $\|\nabla f(x)-\nabla f(z)\|\leq\gamma\|x-z\|\ \forall x,z\in\mathbb{R}^{d}$.

2. O2:

   At time $k$, the oracle is in state $o_{k}\in\{1,\dots,R\}$, where $R$ are the number of oracle states and for the incentive $i_{k}\in\{i^{1},\dots,i^{n_{i}}\}$, replies with probability $\Gamma(o_{k},i_{k})$. $s_{k}\sim\text{Bernoulli}(\Gamma(o_{k},i_{k}))$ denotes success of the reply.

3. O3:

   For a reply with success $s_{k}$ to the query $q_{k}\in\mathbb{R}^{d}$, the oracle returns a noisy gradient response $r_{k}$ according to (1). The noise terms $\eta_{k}$ are independent ²²2A slightly weaker assumption based on conditional independence was considered in our paper [4]. We consider independence here for brevity., have zero-mean and finite-variance, $\mathds{E}[r_{k}]=\nabla f(q_{k})$ and $\mathds{E}[\|\eta_{k}\|^{2}]\leq\sigma^{2}$.

O1 and O3 are standard assumptions for analyzing oracle-based gradient descent [3]. O2 is motivated by an oracle with a stochastic state (e.g., client participation), and the success is determined by the oracle or by the learner.

Similar to oracle-based first-order gradient descent [3], the learner aims to estimate $\hat{x}\in\mathbb{R}^{d}$ which is a $\epsilon$-close critical point of the function $f$,

Since $f$ is non-convex and not known in closed-form to the learner, in general, the gradient at $z_{1}$ is non-informative about the gradient at $z_{2}$ far from $z_{1}$. Hence, at time $k$, the learner can either send a learning or an obfuscating query. We propose controlling the gradient descent of the learner by the query action $a_{k}\in\{0=\texttt{obfuscating},1=\texttt{learning}\}$. While learning, the learner updates its estimate, $\hat{x}_{k}$ by performing the controlled stochastic gradient step of (2). Here, $\mu_{k}$ is the step size chosen to be constant in this paper. In the next section, we will formally state the action space composed of the type of query $a_{k}$ and the incentive $i_{k}$. In order to estimate the number of queries to the oracle that the learner has to spend on learning queries, we first define the successful gradient step. We then state the result on the order of the number of successful gradient steps required for achieving the objective.

Proof for a general setting can be found in [4] and in [3]. Theorem 1 characterizes the number of successful gradient steps, $M$ that the learner needs to perform to achieve the learning objective of (4). Theorem 1 guarantees the existence of a finite queue state space in the next section, which models the number of successful gradient steps left to be taken. $M$ in the MDP formulation of the next section can be chosen heuristically or be computed exactly if the parameters of the function are known. It also shows that $M$ is inversely dependent on $\epsilon$ and incorporates the descent dynamics in the structure of the optimal policy.

Based on the chosen SG $a_{k}$, the learner poses queries using (3) and provides incentives to the oracle. To obfuscate the eavesdropper, the learner runs a parallel stochastic gradient with synthetic responses, $\bar{r}_{k}$. The synthetic responses can be generated by suitably simulating an oracle, for e.g., the learner can train a neural network separately with an unbalanced subset of as was done in [4]. If the learner is sure that the eavesdropper has no public dataset to validate, the learner can simply take mirrored gradients with (1). When obfuscating, the learner poses queries from the estimates of the second SG, $\hat{z}_{k}$.

The parallel stochastic gradient ensures that the eavesdropper cannot infer the true learning trajectory from the shape of the trajectory. In summary, the learner obfuscates and learns by dynamically chooses the query $q_{k}$, as the current estimate $\hat{x}_{k}$ from the controlled stochastic gradient step or as the estimate $\hat{z}_{k}$ of parallel SG. We assume that the learner queries such that the two trajectories are sufficiently separated from each other, and the eavesdropper can cluster the queries and distinguish them uniquely into two trajectories as described next.

At time $k$, the eavesdropper observes query $q_{k}$ and the incentive $i_{k}$ by the learner. We use the following assumptions to approximate the posterior belief of the eavesdropper,

1. E1:

   The eavesdropper is passive, does not affect the oracle, and can not observe the oracle’s responses, $r_{k}$.

2. E2:

   For $k>0$, the eavesdropper can classify each query of the observed query sequence $(q_{1},\dots,q_{k})$ into two unique trajectory sequences, $\mathcal{J}_{1}^{k}$ and $\mathcal{J}_{2}^{k}$ which can be separated by a hyperplane in $\mathbb{R}^{d}$.

3. E3:

   The eavesdropper knows that either of $\mathcal{J}_{1}^{k}$ and $\mathcal{J}_{2}^{k}$ is a learning trajectory. Given the information till time $k$, the eavesdropper computes a posterior belief, $\delta_{k}$ for trajectory $\mathcal{J}_{1}^{k}$ being the learning trajectory as,

   $\displaystyle\delta_{k}=\mathds{P}(\hat{x}\in\mathcal{J}_{1}^{k}|(q_{1},i_{1},\dots,q_{k},i_{k})).$

Assumption E1 holds if the eavesdropper is considered an insignificant part of the oracle and can not observe the aggregated response. Assumptions E2 and E3 ensure the dynamic obfuscation is for a worst-case eavesdropper ³³3As mentioned above, it is assumed that the queries are posed such that the two trajectories are sufficiently separated (by a metric known to the eavesdropper). One of the trajectories can be empty for the initial queries.. We consider the eavesdropper using an incentive-weighed proportional sampling estimator for the posterior $\delta_{k}$ [12, 4],

The learner has access to the queries and the incentives and uses (5) as an approximation for the eavesdropper’s $\arg\min$ estimate to compute the cost incurred when learning. The following section formulates an MDP to perform covert optimization using stochastic control. $M$ from Theorem 1 and oracle state are used to model the state space, while the incentives $i_{k}$ and the type of SG $a_{k}$ in (2) model the action space.

The dynamic programming index, $n=N,\dots,0$ denotes the number of queries left and decreases with time $k$.

State Space: The state space is denoted by $\mathcal{Y}=\mathcal{Y}^{B}\times\mathcal{Y}^{O}$ where $\mathcal{Y}^{B}=\{0,1,\dots,M\}$ is the learner queue state space and $\mathcal{Y}^{O}=\{0,1,\dots,R\}$ is the oracle state space. The learner queue state $b_{n}\in\mathcal{Y}^{B}$ denotes the number of successful gradient steps (Def. 1) remaining to achieve (4). The oracle state space $\mathcal{Y}^{O}$ discretizes the stochastic state of the oracle into $R$ levels (e.g., percentages of client participation in FL). $y_{n}$ denotes the state with $n$ queries remaining.

Action Space: The action space is $\mathcal{U}=\{0=\texttt{obfuscate},1=\texttt{learn}\}\times\{i^{1},\dots,i^{n_{i}}\}$. The action when $n$ queries are remaining is given by, $u_{n}=(a_{n},i_{n})$ where $a_{n}\in\{0=\texttt{obfuscate},1=\texttt{learn}\}$ is the type of the query and $i_{n}\in\{i^{1},\dots,i^{n_{i}}\}$ is the incentive. To derive structural results on the optimal policy, we consider the following transformation of the action space, $\mathcal{U}=\{(0,i^{1}),\dots,(0,i^{n_{i}}),(1,i^{1}),\dots,(1,i^{n_{i}})\}$. A deterministic policy for the finite-horizon MDP is denoted by $\pi$, a sequence of functions $\pi=(u_{n}:n=0,\dots,N)$. Here, $u_{n}:\mathcal{Y}\to\mathcal{U}$ maps the state space to the action space. $\Pi$ denotes the space of all policies.

Transition Probabilities: We assume that the evolution of the oracle state and the learner queue state is Markovian. The oracle state evolves independently of the queue state evolution. In case of a successful gradient step (Def. 1), the queue decreases by one, and the oracle state evolves to a state $o^{\prime}\in\mathcal{Y}^{O}$ with probability $\Delta({o^{\prime}}|{o}){>0}$. Let $\mathcal{P}^{o,o^{\prime}}_{b}(u)=\nicefrac{{\mathds{P}((o^{\prime},\cdot)|o,b,u)}}{{\Delta({o^{\prime}}|{o})}}$ denote the transition probability vector of the buffer state with future oracle state $o^{\prime}$ given $(o,b,u)$. The transition probability from the state $y=(o,b)\in\mathcal{Y}$ to state $y^{\prime}=(o^{\prime},b^{\prime})\in\mathcal{Y}$ with action $u=(a,i)$ can be written as,

and is $0$ otherwise. The first equation corresponds to a successful gradient step, and the second to an unsuccessful one. We assume that $\Gamma(o,i)$ (from O2) is increasing in incentive $i$.

Learning and Queueing Cost: The learning cost $c_{n}:\mathcal{Y}\times\mathcal{U}\to\mathbb{R}$, is the cost (with $n$ queries remaining) incurred after every action due to learning at the expense of reduced obfuscation. We consider the following learning cost which is proportional to the logarithm of the improvement in the eavesdropper’s estimate ($\propto\log(\nicefrac{{\delta_{n}}}{{\delta_{n+1}}})$) and is given by,

where $\psi_{1}:\mathcal{Y}^{B}\to\mathbb{R}^{+}$ and $\psi_{2}:\mathcal{Y}^{O}\to\mathbb{R}^{+}$ are positive, convex and increasing cost functions, $I_{n}=\sum_{k=N-1}^{n+1}i_{k}$ is the sum of the previous incentives and $\delta_{n}$ is the eavesdropper’s estimate of the trajectory $\mathcal{J}_{1}$ being the true trajectory computed using (5). $\psi_{1}$ and $\psi_{2}$ are used to incorporate the cost with respect to the oracle and queue state, e.g., the functions $\psi_{1}$, and $\psi_{2}$ are considered quadratic in the respective states in the experiments. The form of the fractions ensures the structure as discussed next. The first term in (7) denotes the cost incurred in a learning query and is non-negative ($0\leq\delta_{k}\leq 1$). The second term corresponds to an obfuscating query and is non-positive. The cost increases with the queue state and decreases with the oracle state. This incentivizes the learner to drive the system to a smaller queue and learn when the oracle is in a good state. After $N$ queries, the learner pays a terminal queue cost computed using the function $d:\mathcal{Y}\to\mathbb{R}$. The queue cost accounts for learning loss in terms of terminal successful gradient steps left, $b_{0}$.

Remark: The incentive improves the response probability $\Gamma$, but also allows for improved obfuscation than a non-incentivized setup (a high incentive can be used to misdirect the eavesdropper’s belief in (5)).

The expected total cost for the finite-horizon MDP with the initial state $y_{N}\in\mathcal{Y}$ and policy $\pi$ is given by,

The optimization problem is to find the optimal policy $\pi^{*}$,

To define the optimal policy using a recursive equation, we first define the value function, $V_{n}$ with $n$ queries remaining,

Let the optimal policy be $\pi^{*}=(u^{*}_{n})_{n=N}^{1}$, where $u^{*}(\cdot)$ is the optimal action with $n$ remaining queries and is the solution of the following stochastic recursion (Bellman’s equation),

where the Q-function $Q_{n}$ is defined as,

with $n=0,\dots,N$ and $V_{0}(y)=d(y)$. If the transition probabilities are unknown, then Q-learning can be used to estimate the optimal policy of (11). However, the following subsection shows that the optimal policy has a threshold structure, which motivates efficient policy search algorithms.

The following is assumed to derive the structural results,

1. R1:

   The learning cost, $c_{n}$ is $\uparrow$ (increasing) and convex in the buffer state, $d_{n}$ for each action $u_{n}\in\mathcal{U}$.

2. R2:

   Transition probability matrix $\mathds{P}(b^{\prime}|b,o,u)$ is TP3⁴⁴4Totally postive of order 3 (TP3) for a matrix P(a) requires that each of 3rd order minor of P(a) is non-negative. with $\sum_{b^{\prime}}b^{\prime}\mathds{P}(b^{\prime}|b,o,u)\uparrow b$ and convex in $b$.

3. R3:

   The terminal cost, $d$ is $\uparrow$ and convex in the queue state, $b$.

4. R4:

   For $\alpha_{b^{\prime},b,u}>0$ and $\uparrow u$, $c(b^{\prime},o,u+1)-c(b^{\prime},o,u)\leq\alpha_{b^{\prime},b,u}(c(b,o,u+1)-c(b,o,u))$, $b^{\prime}>b$.

5. R5:

   For $\beta_{b^{\prime},b,u}>0$ and $\uparrow u$,

   $\frac{\mathcal{P}^{o,o^{\prime}}_{b^{\prime}}(u+1)+\beta_{b^{\prime},b,u}\mathcal{P}^{o,o^{\prime}}_{b^{\prime}}(u)}{1+\beta_{b^{\prime},b,u}}<_{c}\frac{\mathcal{P}^{o,o^{\prime}}_{b}(u)+\beta_{b^{\prime},b,u}\mathcal{P}^{o,o^{\prime}}_{b}(u+1)}{1+\beta_{b^{\prime},b,u}}$

   $,b^{\prime}>b,\forall o^{\prime},o\in\mathcal{Y}^{O}$; $<_{c}$ denotes convex dominance ⁵⁵5Probability vector $p$ is convex dominated by probability vector $q$ iff $f^{\prime}p\geq f^{\prime}q$ for increasing and convex vector $f$..

6. R6:

   There exist $\alpha_{b^{\prime},b,u}=\beta_{b^{\prime},b,u}$ s.t. (R4) and (R5) hold.

Assumptions (R1) and (R3) are true by the construction of cost in (7) and the terminal cost. (R2) is a standard assumption on bi-diagonal stochastic matrices made when analyzing structural results [5]. (R4), (R5) and (R6) are the generalization of the supermodularity conditions made previously in [4] and are sufficient for interval dominance [5]. Assumption (R4) can be verified for cost of (7) using algebraic manipulation with $\alpha_{b^{\prime},b,u}\leq 1$, and (R5) can be shown with $\beta_{b^{\prime},b,u}\leq 1$ for the bi-diagonal matrix of  (6) with $\Gamma(o,i)\uparrow i$. Therefore (R6) can be satisfied for some $\gamma_{b^{\prime},b,u}=\alpha_{b^{\prime},b,u}=\beta_{b^{\prime},b,u}\leq 1$. We now state the main structural result,

Theorem 2 implies that the policy is threshold in the learner queue state; hence, the learner learns more aggressively when the number of successful gradient steps (Def. 1) left is more. This intuitively makes sense from an obfuscation perspective since the learner should ideally spend more time obfuscating when it is closer to the minimizer (the queue state is small).

Using Theorem 2, we can parameterize the optimal policy by the thresholds on the queue state. Although we can construct stochastic approximation for estimating the non-stationary policy, which has a threshold structure and performs computationally better than Q-learning, this approach still requires the number of parameters to be linear in time horizon $N$. Given this insight, we restrict the search space to stationary policies with a monotone threshold structure, this restriction is common in literature [4, 7].

Let the threshold on queue state for oracle state $o$ and action $u$ be parameterized by $\bar{b}:\mathcal{Y}^{O}\times\mathcal{U}\to\mathcal{Y}^{B}$. The optimal stationary policy with a threshold structure can be written as,

where $\bar{b}^{*}$ is the optimal threshold function.

Taking the thresholds of the stationary policy of  (14) as the parameters, a simultaneous perturbation stochastic approximation (SPSA) based algorithm can be used to find the parameters for the optimal policy. We update the policy parameters using approximate gradients of the costs computed using perturbed parameters. We use the following sigmoidal approximation for the threshold policy of (14),

where $\tau$ is an approximation parameter. The parameters are the $F=|\mathcal{U}||\mathcal{Y}_{O}|$ threshold values and are represented by $\Theta$. For the optimal parameters, the approximate policy converges to the optimal policy as $\tau\to 0$ [7]. For the learning episode $i$ and current parameter set $\Theta_{i}$, the actions are computed using the current approximate policy (15). The policy parameters are perturbed independently with probability $\nicefrac{{1}}{{2}}$ by $\pm\delta$. Two learning episodes are performed with each set of perturbed policy parameters ($\Theta_{i}^{+}$,$\Theta_{i}^{-}$). The costs from the two episodes are used to obtain the approximate gradient $\tilde{\nabla}C_{i}$ by the method of finite differences. The policy parameters are updated using a stepsize $\phi_{i}$,

Under regularity conditions on the noise in the approximate gradients, the approximate policy parameters asymptotically converge in distribution to the set of parameters of the optimal stationary policies with a threshold structure [6]. The SPSA algorithm can also be used with a constant step size to track changes in the system [4, 6]. The computational complexity for each learning episode is $O(F+N)$.

The problem of searching the thresholds for (14) is solved by considering the values each threshold can take and then taking the product space of the thresholds as bandit arms. Each threshold can take values over learner state space $\mathcal{Y}_{B}$, which is of the cardinality $M+1$. Consider each permutation of the $F=|\mathcal{U}||\mathcal{Y}_{O}|$ thresholds as an arm, making the total number of arms $(M+1)^{F}$. The selection of an arm gives a corresponding stationary policy of the form (11), and a reward (negative of the cumulative cost of the episode) is obtained by interacting with oracle for time horizon $N$. The noisy reward is sampled from a distribution centered at the expected value (8). (B1) The reward is assumed to be sampled independently for a given policy, and the noise is assumed to be sub-Gaussian [2]. For brevity, we omit the definition of regret and the exact upper bound, both of which can be found in Chapter 2 of  [2]. Following is the result for the upper bound on the regret for searching the thresholds,

The proof follows from Theorem 1 and plugging the number of arms in the standard regret bound for UCB [2]. Although the regret for this approach is bounded, the significant limitations are that the bound is exponential in the state and action space and, compared to SPSA, it cannot track changes in the system.