# Policy Optimization with Advantage Regularization for Long-Term Fairness in
Decision Systems

Eric Yang Yu
UC San Diego
&Zhizhen Qin
UC San Diego
&Min Kyung Lee
UT Austin
&Sicun Gao
UC San Diego

###### Abstract

Long-term fairness is an important factor of consideration in designing and
deploying learning-based decision systems in high-stake decision-making
contexts. Recent work has proposed the use of Markov Decision Processes (MDPs)
to formulate decision-making with long-term fairness requirements in
dynamically changing environments, and demonstrated major challenges in
directly deploying heuristic and rule-based policies that worked well in
static environments. We show that policy optimization methods from deep
reinforcement learning can be used to find strictly better decision policies
that can often achieve both higher overall utility and less violation of the
fairness requirements, compared to previously-known strategies. In particular,
we propose new methods for imposing fairness requirements in policy
optimization by regularizing the advantage evaluation of different actions.
Our proposed methods make it easy to impose fairness constraints without
reward engineering or sacrificing training efficiency. We perform detailed
analyses in three established case studies, including attention allocation in
incident monitoring, bank loan approval, and vaccine distribution in
population networks.

##  1 Introduction

Learning-based algorithmic decision systems are increasingly used in high-
stake decision-making contexts. A critical factor of consideration in their
design and deployment is to ensure fairness and avoid disparate impacts on the
marginalized populations [25]. Although many approaches have been developed to
study and ensure fairness in algorithmic decision systems [25, 13], most of
the literature studies fair decision-making in a one-shot context, meaning
they make the decision that maximizes fairness in a static setting. This
approach fails to explicitly address how decisions made in the present may
affect the future status and behaviors of targeted groups, which in turn can
form a feedback loop that negatively impacts the effectiveness and fairness of
the decision-making strategies. In other words, the implications associated
with _long-term fairness_ , or fairness evaluated over a time horizon rather
than in a single time step, are largely under-studied.

The long-term impact of such decision systems has recently been explored
through explicit modeling of the dynamics and feedback effects in the
interactions between the decision-makers and the targeted populations [16, 28,
35, 24, 14]. In particular, the recent work of [16] has demonstrated, with
concrete simulation examples, how long-term fairness can not be analyzed in
closed forms, but requires the use of more computational analysis tools based
on simulations. They proposed to formulate such long-term dynamics and the
interaction between the decision-making and the environment in the framework
of Markov Decision Processes (MDPs). This formulation and the corresponding
simulation environments make it possible to take advantage of recent advances
in deep reinforcement learning (RL) for finding new decision-making policies
that can achieve both better overall utility and fairness, compared to
manually designed heuristic and rule-based strategies.

One challenge of directly using RL-based methods for learning decision-making
policies, however, is that the goal of decision systems in the high-stake
decision-making context is often inherently multi-objective. On one hand, from
a utilitarian perspective, an effective policy should try to maximize the
overall expected utility of the decisions for all targeted groups. On the
other hand, constraints such as the fairness requirements should be explicitly
enforced to prevent biased policies that negatively treat certain groups in
temporary or historically disadvantageous situations. Since the standard RL
framework for policy optimization only optimizes a policy with respect to a
monolithic reward function, it can be difficult to enforce these fairness
requirements during training. An intuitive approach for enforcing fairness in
standard RL is to define a penalty term in the objective function that
captures the magnitude of violation of the fairness requirements by the
policy. However, this approach would require the RL user to define the trade-
off between the utilitarian objective and the fairness objective, typically as
weights on each objective. This requirement of _reward engineering_ can make
it hard to justify the policies obtained by the RL algorithms, because one can
question whether the predefined weights have introduced problematic
assumptions and trade-offs between the objectives in the first place. The
monolithic reward definitions may also incentivize the learning agent to
perform _reward hacking_ [29], or adopt undesirable behaviors that exploit the
wrong trade-off between the different objectives, such as conservatively
accumulating incremental rewards without achieving the overall goal just to
avoid the penalty of violating constraints.

One approach for addressing such problems is the framework of Constrained
Markov Decision Processes (CMDPs) [2], which allows the RL user to explicitly
declare rewards and constraints and use RL algorithms such as Constrained
Policy Optimization (CPO) [1] to simultaneously maximize reward and minimize
constraint violation over time. However, the CMDP formulation only requires
the learning algorithms to lower the expectation of constraint violation
asymptotically, i.e. achieving constraint-abiding policies in a probabilistic
sense if training time is allowed to be infinitely long, and can not ensure
fairness for policies trained in practice. Moreover, in comparison to standard
policy optimization methods such as Proximal Policy Optimization (PPO) [31],
algorithms for CMDPs can take significantly longer, and the policies obtained
after finite training periods may still have high constraint-violation rates
and poor performance.

We propose new methods for enforcing long-term fairness properties in decision
systems by taking a constrained RL approach. At a high level, we enforce
fairness requirements at the policy gradient level during policy optimization
with minimal additional computational overhead. By enforcing fairness
constraints through advantage regularization rather than at the objective
level, we avoid reward engineering or hacking on the decision problems and aim
to algorithmically optimize the trade-off between utility and fairness. At the
same time, the proposed learning algorithms can train the decision policies
much more efficiently than existing CMDP methods. Finally, the simplicity of
our approach enables easy integration with off-the-shelf policy optimization
algorithms in RL. Our methods are inspired by Lyapunov stability methods for
improving stability in control systems [19, 30, 23, 4, 7, 6]. We show that
fairness properties can be handled in a similar framework with our specific
design of the constraint regularization terms. In sum, our main contributions
are as follows:

$\bullet$ We show that RL approaches are effective for designing policies that
can achieve long-term fairness, where existing heuristic and rule-based
approaches do not perform well [16]. Specifically, we demonstrate that policy
optimization methods can find strictly better decision policies that achieve
higher overall utility and violate less of the fairness requirements than
previously-known strategies.

$\bullet$ We propose novel methods for imposing fairness requirements in
standard policy optimization procedures by regularizing the advantage
evaluation during the policy gradient steps. This approach uses control-
theoretic frameworks to enforce fairness constraints and avoids reward
engineering issues in the decision-making context [16].

We evaluate our approaches in several established case studies using the
simulation environments [16, 3], such as incident monitoring, bank loan
approval, and vaccine distribution for infectious diseases in population
networks. We find that the proposed policy optimization with advantage
regularization is able to find policies that perform better than previously-
known strategies, both in achieving higher overall utility and lower violation
of the fairness requirements in all the case study environments.

##  2 Related Work

#### Long-term Fairness in Algorithmic Decision-Making.

The work in [16] is the first to formulate long-term fairness problems in
decision systems as Markov Decision Processes (MDPs). The simulation
environments proposed in the work allow us to consider the agent design
problem in ways that are to other RL problems such as robot control. Others
have also shown that long-term fairness is nontrivial, and analyzing it in the
context of a static scenario can be harmful because it contradicts fairness
objectives optimized in static settings [21, 22, 26]. For example, [21, 26]
find that providing a direct subsidy for a disadvantaged group with the
purpose of improving some institutional utility actually widens the gap
between advantaged and disadvantaged groups over time, which further shows
that long-term fairness is difficult to achieve. There have been a growing
number of studies on fairness in the long-term with various algorithmic
approaches [28, 35, 24, 14]. [24] proposes a graph-based algorithm to improve
fairness in recommendations for items and suppliers. They relate fairness to
breaking the perpetuation of bias in the interactions between users and items.
[14] proposes the use of causal directed acyclic graphs (DAGs) as a paradigm
for studying fairness in dynamical systems. They argue that causal reasoning
can help improve the fairness of off-policy learning, and if the underlying
environment dynamics are known, causal DAGs can be used as simulators for the
models in training. [35] provides a framework for studying long-term fairness
and finds that static fairness constraints can either promote fairness or
increase disparity between advantaged and disadvantaged groups in dynamical
systems. [17] studies how to maintain long-term fairness on item exposure for
the task of splitting items into groups by recommendation, using a modified
Constrained Policy Optimization (CPO) procedure [1]. [9] introduces the
fairness notion of return parity, a measure of the similarity in expected
returns across different demographic groups, and provides an algorithm for
minimizing this disparity.

Several recent works have also considered fairness-like constraints in deep
reinforcement learning in various different contexts. [8] designs fairness
optimized actor-critic algorithms in deep reinforcement learning. They enforce
fairness by multiplicatively adjusting the reward for fairness utility
optimization in standard actor-critic reinforcement learning. The work of [32]
studied multi-dimensional reward functions for MDPs motivated by fairness and
equality constraints, and performed theoretical analysis on the approximation
error with respect to the optimal average reward. Our focus is on proposing a
practical algorithm for making fair decisions in the dynamic environments
formulated in [16] and show that policy optimization through advantage
regularization can find the neural network policies that significantly
outperform previously known strategies in the dynamic setting.

#### Policy Optimization under Constraints.

The most widely-adopted formulation of RL with a set of constraints is
constrained Markov Decision Processes (CMDPs) [2, 34]. Safety constraints are
incorporated by augmenting the standard MDP framework with constraints over
expectations of auxiliary costs. When models are known in discrete tabular
settings, a CMDP is solvable using linear programming (LP) [2]. However,
results are limited for model-free scenarios where model dynamics are unknown,
and for large-scale or even continuous state action spaces [1, 11, 34]. More
importantly, both objective and constraint in high-dimensional CMDP settings,
where high-capacity function approximators are adopted, are non-convex. Recent
methods in solving CMDPs in continuous spaces can be divided into two
categories, in terms of ways to incorporate constraints. In soft constrained
RL, it is a common practice to apply Lagrangian method with learnable
Lagrangian multipliers and solve the converted unconstrained saddle-point
optimization problem using policy-based methods [5, 10, 33]. Such Lagrangian
methods achieve overall safety when policies converge asymptotically,
nevertheless allowing possible violations during training. On the contrary,
hard-constrained RL aims to learn safe policies throughout training.
Representative works include Constrained Policy Optimization (CPO) based on
trust region [1], surrogate algorithms with stepwise [15] and super-martingale
[27] surrogate constraints, as well as Lyapunov-based approaches [11, 12].

##  3 Policy Optimization with Advantage Regularization

In long-term fairness studies [16], fairness is evaluated over a time horizon
where the agent interacts with the environment, and the environment can change
in response to the interactions. Simulations following the MDP framework is
one way to analyze fairness over time and systematically come up with
strategies for maximizing fairness in the long-term rather than in a single
step. MDPs naturally incorporate the idea that actions made in the present can
have accumulating consequences on the environment over time. Long-term
fairness is evaluated with metrics that describe the consequences made by an
agent’s policy on the different subgroups in an environment over time. These
metrics are computed at each step of the MDP, and include data collected from
the past time steps.

#### Policy Optimization in MDPs.

Formally, an MDP is defined as
$M=\langle\mathcal{S},\mathcal{A},f,r,\gamma\rangle$ with the following
components. $\mathcal{S}$ denotes the state space, and $\mathcal{A}$ the
action space. The transition function
$f:\mathcal{S}\times\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ determines
the probability $f(s^{\prime}|s,a)$ of transitioning into state $s^{\prime}$
from state $s$ after taking action $a$. We consider general forms of reward
functions
$r:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$ defined
over transitions. We write $\pi_{\theta}$ to denote a stochastic policy
$\pi_{\theta}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ parameterized by
$\theta$. The goal of policy optimization is to maximize the expected
$\gamma$-discounted cumulative return

$J(\theta)=\mathbb{E}_{s_{0},a_{0},\ldots}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t},s_{t+1})\right].$
(1)

Policy optimization methods estimate the policy gradient and use stochastic
gradient ascent to directly improve policy performance. A standard gradient
estimator is to use $\nabla_{\theta}\log\pi_{\theta}(a_{t}|s_{t})\hat{A}_{t}$,
where $\pi_{\theta}$ is a stochastic policy and $\hat{A}_{t}$ estimates the
advantage that represents the difference between the Q value of an action
compared with the expected value of a state, to indicate whether an action
should be taken more frequently in the future. The gradient steps will move
the distribution over actions in the right direction accordingly. The
expectation is estimated by the empirical average over finite batch of
samples. The proximal policy optimization algorithm (PPO) [31] applies
clipping to the objective function to remove incentives for the policy to
change dramatically, using:

$J^{\rm
CLIP}(\theta)\leftarrow\hat{\mathbb{E}}\left[\min\left(R_{t}(\theta)\hat{A}_{t},{\rm
clip}(R_{t}(\theta),1-\epsilon,1+\epsilon)\hat{A}_{t}\right)\right],$ (2)

where
$R_{t}(\theta)=\pi_{\theta}(a_{t}|s_{t})/\pi_{\theta_{\textit{old}}}(a_{t}|s_{t})$
and $\epsilon$ is a hyperparameter. The clipping ensures the gradient steps do
not overshoot in the policy parameter space in each policy update.

Algorithm 1 Policy Optimization with Constraint Advantage Regularization
(POCAR)

1:Initialize policy network $\pi_{\theta}$ and value function network
$V_{\phi}$

2:for $k=1,2\dots$ do

3: Initialize replay buffer $B$ as $\emptyset$

4: for $\text{episode }=1,\dots,E$ do

5: for $t=1,2\dots,T$ do

6: Sample $a_{t}\sim\pi_{\theta}(a_{t}|s_{t})$

7: Sample $s_{t+1}\sim f(s_{t+1}|s_{t},a_{t})$

8: Compute $\Delta_{t}\equiv\Delta(s_{t})\text{ and
}\Delta_{t+1}\equiv\Delta(s_{t+1})$

9: $B\leftarrow B\cup\\{s_{t},a_{t},r_{t},s_{t+1},\Delta_{t},\Delta_{t+1}\\}$

10: end for

11: end for

12: for each policy gradient step do

13: Sample mini-batch
$\\{s_{t},a_{t},r_{t},s_{t+1},\Delta_{t},\Delta_{t+1}\\}^{N}$ from $B$

14: Compute advantages $\hat{A}(s_{t},a_{t})$ (using any advantage
approximation method) based on $V_{\phi_{k}}$

15:
$\hat{A}_{\beta}(s_{t},a_{t})\leftarrow\beta_{0}\hat{A}(s_{t},a_{t})+\beta_{1}\text{min}(0,-\Delta_{t}+\omega)+\beta_{2}\begin{cases}\text{min}(0,\Delta_{t}-\Delta_{t+1})&\text{if
}\Delta_{t}>\omega\\\ 0&\text{otherwise}\\\ \end{cases}$

16:
$R_{t}(\theta)\leftarrow\pi_{\theta}(s_{t},a_{t})/\pi_{\theta_{k}}(s_{t},a_{t})$

17: $J^{\rm
CLIP}(\theta,\beta)\leftarrow\hat{\mathbb{E}}\left[\text{min}\left(R_{t}(\theta)\hat{A}_{\beta}(s_{t},a_{t}),\rm
clip\left(R_{t}(\theta),1-\epsilon,1+\epsilon\right)\hat{A}_{\beta}(s_{t},a_{t})\right)\right]$

18: $\theta\leftarrow\theta+\alpha_{\theta}\nabla_{\theta}J^{\rm
CLIP}(\theta,\beta)$

19:
$\phi\leftarrow\phi+\alpha_{\phi}\nabla_{\phi}\hat{\mathbb{E}}\left[(V_{\phi}(s_{t})-G(s_{t}))^{2}\right]$
$\triangleright$ $G(s_{t})\leftarrow\sum^{T}_{i=0}\gamma^{i}r_{t+i}$

20: end for

21:end for

#### Fairness Constraint Advantage Regularization.

We modify the PPO algorithm to be fairness-constrained during policy
optimization in the following way. First, in addition to the original MDP with
only the overall utility as reward function $r$, we declare a separate
fairness metric $\Delta:S\rightarrow\mathbb{R}^{\geq}$ as a function of the
state, where smaller $\Delta$-value indicate better satisfaction of the
fairness constraints. We then task the PPO algorithm to learn a decision
policy to maximize the expected discounted future return $J$, while regulating
the advantage term to decrease $\Delta$-value in each step. Suppose fairness
at a particular time step can be modeled by the fairness constraint metric
$\Delta(s_{t})$. We minimize this term by modifying the advantage function in
PPO to:

$\hat{A}_{\beta}(s_{t},a_{t})=\beta_{0}\hat{A}(s_{t},a_{t})+\beta_{1}\text{min}(0,-\Delta(s_{t})+\omega)+\beta_{2}\begin{cases}\text{min}(0,\Delta(s_{t})-\Delta(s_{t+1}))&\text{if
}\Delta(s_{t})>\omega\\\ 0&\text{otherwise}\\\ \end{cases}$ (3)

where $\hat{A}(s_{t},a_{t})$ is the original PPO advantage. The two terms
added to the original advantage estimator are designed as follows.

$\bullet$ The value-thresholding term $\min(0,-\Delta(s_{t})+\omega)$
penalizes the advantage value for $(s_{t},a_{t})$ if the fairness metric
$\Delta(s_{t})$ is too high. That is, if it is higher than some threshold
$\omega$, then this term evaluates to a negative value. On the other hand, if
$\Delta(s_{t})$ is already less than $\omega$, then the term evaluates to
zero, and does not affect the advantage value. On a high level, this term
transforms the advantage landscape by adding a region of attraction around
some equilibrium point, which specifies a tolerable violation of $\Delta$.

$\bullet$ The decrease-in-violation term
$\text{min}(0,\Delta(s_{t})-\Delta(s_{t+1}))$ is activated when the value of
$\Delta(s_{t})$ is larger than the tolerable threshold $\omega$. When that is
the case, this term penalizes the overall advantage if the degree of fairness
violation does not decrease in the transition from $s_{t}$ to $s_{t+1}$. If
either the violation is decreasing or is less than $\omega$, then this term
does not affect the overall advantage. The decrease-in-violation term imposes
the soft requirement of negative-definiteness of Lie derivatives in the
standard Lyapunov conditions. Here we use the the finite difference of
$\Delta(s_{t})-\Delta(s_{t+1})$ to measure the dynamics of the fairness metric
over time.

For both of the advantage regularization terms, the hyperparameters
$\omega,\beta_{0},\beta_{1},$ and $\beta_{2}$ are positive numbers that can be
tuned. The design of these terms uses the idea of Lyapunov stability [19],
which is a powerful framework in control theory for stabilization problems
such as reducing the error signal, which can be used to model the violation of
the fairness requirement over time.

The full pseudocode for policy optimization with advantage regularization is
shown in Algorithm 1. At each iteration of the policy update loop (Lines
2-21), we sample trajectories from the system $f$, and compute the fairness
constraint $\Delta(s_{t})$ and $\Delta(s_{t+1})$ (Line 8) to save into buffer
$B$ alongside state $s_{t}$, action $a_{t}$, reward $s_{t}$, and next state
$s_{t+1}$ (Line 9). In each policy update step, we modify the advantage
function to include the two additional fairness regularization terms as
described above.

#### Connection with Lyapunov Methods for Stabilization Control.

In the proposed methods, we are essentially considering the problem of
ensuring long-term fairness as a control problem: the goal is to obtain a
control policy to regulate the entire system to improve its satisfaction of
the fairness properties over time. Consequently, we are implicitly using
control-theoretic methods from the Lyapunov stability framework [19, 6, 30,
23, 4] in our approach, because long-term fairness is essentially about
stability properties: we wish to control the system such that the violation of
fairness reduces over time, and ideally gets controlled to be under a certain
threshold. This connection makes it possible to use Lyapunov methods to derive
the regularization terms. A brief introduction to the theory behind Lyapunov
stability is provided in Section A of the Appendix.

##  4 Experiments

We evaluate the proposed approaches in three case studies as proposed in [16,
3], including attention allocation for incident monitoring, credit approval
for lending, and disease control in population networks. In all environments,
we compare the performance of policies found by the proposed methods with
known human-designed policies, or strategies designed by humans that do not
involve any learning-based algorithmic design. We also compare different ways
of imposing the fairness constraints in the policy optimization procedures, as
well as the Constrained Policy Optimization (CPO) [1] approach, to evaluate
the effectiveness of advantage regularization techniques.

First, we broadly define several common agents across the experiments. The
greedy baseline agent, as the name suggests, is a human-designed policy that
maximizes for some objective without any fairness constraints. The CPO agent
is a closely-related RL baseline for us to compare our advantage
regularization approach with. For our proposed method, we evaluate three
variations of PPO-based policy optimization: Greedy PPO (G-PPO) greedily
maximizes the objective without any fairness constraints, Reward-Only Fairness
Constrained PPO (R-PPO) is fairness constrained only at the reward level by
adding some variation of $-\text{max}(0,\Delta_{t}-\omega)$ to the reward
function where $\omega$ thresholds the fairness constraint, and Advantage
Regularization PPO (A-PPO) is fairness constrained only at the policy gradient
level by applying Equation 3 to PPO during training. Going forward, we will be
referring to these three PPO variations and their definitions by their short-
hand notations (G-PPO, R-PPO and A-PPO) for all experiments.

###  4.1 Case Study: Attention Allocation for Incident Monitoring

We first consider the problem of attention allocation in a dynamic setting,
formulated as an MDP in [16]. In this problem, an agent is tasked with
discovering incidents across several sites, and does not have a large enough
attention span to cover all incidents occurring at any given moment. The site
incident rates increase or decrease proportional to the allocated site
attention, making the environment dynamic. We find that training an RL agent
in this environment outperforms the human-designed policy in both utility and
fairness over time. Moreover, we modified the environment to be harder, where
the previously known policies perform significantly worse. We show that policy
optimization with advantage regularization continues to work well in the
harder environments as well.

#### Environment.

Let $a_{kt}$ be the discrete attention allocated toward site $k$ at time $t$,
and $R_{kt}$ be the incident rate. At each time step, the agent assigns $N$
discrete units of attention across $K$ sites. The number of incidents occurred
at each site is sampled $y_{kt}\sim\mbox{Poisson}(R_{kt})$ and number of
incidents discovered at each site is $\hat{y}_{kt}:=\min(a_{kt},y_{kt})$. The
incident rates change proportional to the attention allocated to each site: if
$a_{k,t}=0$, then $R_{k,t+1}=R_{k,t}+d$, otherwise $R_{k,t+1}=R_{k,t}-d\cdot
a_{k,t}$, where $d$ is the parameter that controls how dynamic the environment
is. The reward function promotes incident discovery and penalizes for
incidents missed. It is defined
$r(s_{t})=\zeta_{0}\sum_{k}\hat{y}_{kt}-\zeta_{1}\sum_{k}(y_{kt}-\hat{y}_{kt}),$
where $\zeta$ is a vector of reward weights.

#### Fairness Constraint.

The fairness metric to be minimized is:

$\Delta(s_{t}):=\text{max}_{k,k^{\prime}}\bigg{|}\frac{\sum_{t}\hat{y}_{kt}}{\sum_{t}y_{kt}+1}-\frac{\sum_{t}\hat{y}_{k^{\prime}t}}{\sum_{t}y_{k^{\prime}t}+1}\bigg{|}.$
(4)

which measures the maximum difference in the ratios between total incidents
discovered and total incidents occurred across all sites.

#### Agents.

Our baseline agents include the CPO agent and the purely greedy agent [16],
which discovers the most incidents and is considered the most fair out of all
agents as evaluated in [16]. The purely greedy agent approximates each site’s
incident rate and sequentially allocates each unit of attention to the site
that has the highest probability of inciting an incident to occur. We compare
these baselines with the G-PPO, R-PPO, and A-PPO variations defined above.

#### Results.

Figure 1: The agent reward over time, average incident rate across all sites
over time, and delta summary evaluated over 10 trials for the base and harder
attention allocation environments. All policy optimization algorithms,
including the CPO agent, outperform the purely greedy agent in both reward and
fairness. In the harder environment, the purely greedy policy collapses in
performance, and we observe how advantage regularization can be a robust form
of imposing fairness.

We begin our experiments with first evaluating on the base attention
allocation environment, where $d=0.1$, $N=6$, and $k=5$. We observe more
interesting results by evaluating on the harder attention allocation
environment, i.e. changing $k=10$.

In the base attention allocation environment in Figure 1, every PPO variation
outperforms the baseline purely greedy agent in terms of reward over time.
G-PPO does not perform as well as R-PPO or A-PPO, which is expected because
the evaluation metric includes the fairness constraint term. Although A-PPO
also does not have a fairness term in the objective, having advantage
regularization in this setting allows A-PPO to perform just as well as R-PPO.
In terms of fairness, we observe that G-PPO is the least fair agent as
expected. Although the purely greedy agent does become the most fair agent at
the end of the trajectory, R-PPO and A-PPO are more consistent in how fair
they are on average over the entire trajectory. We observe that the CPO agent
does not perform well on the base environment, because its incident rates get
pushed to 0 early on in the trajectory in Figure 1.

To analyze why PPO outperforms the purely greedy agent in reward and fairness,
we need to interpret their behaviors in Figure 1. Here, we observe that the
average incident rate for the purely greedy agent is much higher than that of
the PPO agent, so it will miss more incidents. The purely greedy agent’s
incident rate also has the highest standard deviation, which is consistent
with the greedy agent’s behavior of focusing all its attention on each site
sequentially. By reducing the incident rate of a single site at a time but
increasing the incident rates at all other sites, the purely greedy agent
pushes the incident rates across sites to oscillate. After becoming well-
trained, the PPO agents find that refining control on the incident rates
across sites in this range allow the agents to maximize on the objective while
being consistently fair.

Since any attention placed on a site means the site’s incident rate goes down,
it is possible to push all site incident rates to 0 if $K\geq N$. However,
what happens if we modify the environment such that $N<K$ and the agent is
unable to decrease the incident rates across all sites at once? After
evaluating on this harder environment, our results become more interesting.

In the second row of Figure 1 A-PPO now performs significantly better than
R-PPO, both of which achieve higher rewards over time than G-PPO. The CPO
agent also does very well, and actually exceeds A-PPO in reward over time in
the beginning of the trajectory. However, the purely greedy policy collapses
in performance. To understand the cause of the baseline failing, we look at
Figure 1. We see that the average incident rate in the purely greedy agent’s
evaluation shoots up uncontrollably. This is a stark contrast from its
evaluation on the base environment, and reveals how this policy may be
sensitive to slight changes in the problem setup. The PPO agents remain
relatively consistent in their strategy, and still push the incident rates to
a range in which they can exert a more refined control on the sites. In terms
of fairness, incorporating advantage regularization allows A-PPO to be more
fair than R-PPO as observed in Figure 1. Purely greedy agent, despite
collapsing in performance, is more fair than the R-PPO and G-PPO. The CPO
agent is also very fair, and actually matches performance with A-PPO. This
tells us that our A-PPO is at least as good as the CPO agent, and can be a
very favorable alternative considering how theoretically it takes longer to
train the CPO agent. In fact, in this experiment we found that empirically our
PPO agent trained 2-3x faster on average than the CPO agent.

We find that in this experiment, decision policies obtained from policy
optimization methods clearly outperform the human-designed policies in both
reward and fairness. Incorporating advantage regularization for fairness
performs better than only having a fairness term in the reward. Advantage
regularization also appears to be more robust since in a harder environment,
A-PPO is able to perform the best.

###  4.2 Case Study: Credit Approval for Lending

Next, we consider credit approval for lending in a dynamic setting [16]. In
this environment, the agent plays the role of the bank and is tasked with
deciding whether to accept or reject loan requests from a pool of applicants.
These decisions affect the underlying population distribution for future time
steps. In our experiments, we find that PPO agents are able to perform well
without the oracle access to the underlying environment, with performance on
par with the baseline strategies that need to make use of such ground-truth
information. A-PPO is still the best policy optimization approach, though the
gap between A-PPO and R-PPO is smaller than the previous example because the
task is simpler.

#### Environment.

The agent is presented a stream of loan applicants, each with a discrete
credit score $C\in\\{1,2,...,C_{\text{max}}\\}$ and some group membership
variable $g\in\\{1,2\\}$. Group 2 is considered disadvantaged compared to
Group 1 with a lower mean of the initial credit score compared to Group 2.
Applicants are uniformly sampled from these two groups. The environment
dynamics change in response to the bank decision (accept or reject) and
applicant decision (repay or default). If a loan request is accepted, the
probability that an applicant pays the bank back is given by the underlying
deterministic function of credit score $\eta(C)$. The higher the applicant
credit score, the more likely they are to pay the bank back. The reward
function encourages high bank profits and is defined
$r(s_{t})=\zeta_{0}(B_{t+1}-B_{t})$ where $B$ represents the bank’s total cash
reserve.

#### Fairness Constraint.

The fairness constraint is defined as
$\Delta(s_{t})=\text{max}_{g,g^{\prime}}|\text{TPR}_{gt}-\text{TPR}_{g^{\prime}t}|$,
where $\text{TPR}_{g}$ is the true positive rate
$\frac{\text{TP}}{\text{TP}+\text{FN}}$ for group $g$. TP is the number of
true positives corresponding to when the agent accepts a loan request and the
loan is repaid, and FN is the number of false negatives corresponding to when
the agent rejects a loan request and the applicant would have repaid.

#### Agents.

We have two baseline policies following the human-designed lending policies in
[16]. Our first baseline agent is the greedy policy that attempts to maximize
bank profits. The second baseline agent is the equality of opportunity (EO)
agent [20], which maximizes bank profits with the constraint of equalizing the
TPRs between the two groups. We note that to simplify the task, [16] gives the
EO agent oracle access to the underlying distribution of credit scores amongst
both groups and the exact repayment probabilities function $\eta$. We later
show that RL is able to achieve similar, if not better, performance compared
with the EO agent even without access to the underlying environment
information. We also include the CPO agent as our secondary fairness-
constrained deep RL baseline.

The PPO agent observation is the applicant data consisting of their credit
score $C$ and group membership variable $g$. The action is a binary decision
for whether to accept or reject an applicant’s loan request. Like in the
attention allocation environment, we evaluate the three previously defined PPO
variations (G-PPO, R-PPO, A-PPO), but for added stability during training, we
apply a min-max normalization to each term in Equation 3 for A-PPO before
performing their weighted sum.

#### Results.

Figure 2: The bank cash over time, loans over time, and delta plots from
evaluating on the lending experiment for 10 trials. We note that in this
experiment, the PPO variations make more profits on average than the baseline
algorithms. Although the EO policy is the most fair and makes a big profit
over time, the A-PPO still out-earns the EO policy and is able to maintain a
competitive level of fairness without having oracle access to underlying
environment information. The CPO agent is one of the most fair agents, but
fails to profit.

We run experiments with $C_{\text{max}}=7$. From Figure 2, it is interesting
to see that all the fairness constrained agents except CPO make a bigger
profit than the fairness unconstrained agents like G-PPO and greedy. To
understand this trend, we look at the average number of loans made across
groups by each agent in Figure 2. We see that the profit an agent makes
roughly correlates to how many loans they give out on average. This makes
sense since an agent cannot make money unless it gives out loans, and the
agents that give out more loans can be interpret as more willing to take risks
for higher rewards.

###  4.3 Case Study: Infectious Disease Control in Population Networks

In our third experiment, we analyze the precision disease control problem [3].
In this problem, the agent’s task is to vaccinate individuals within a social
network to minimize the spread of a disease. In this experiment, we observe
that the PPO variations still outperform the human-designed policies in both
utility and overall fairness. Integrating advantage regularization appears to
have an equal effect as constraining fairness at the reward level only, which
we analyze later. The CPO agent fails to perform well on this environment.

#### Environment.

A social network $N$ is composed of individuals $V$ connected with edges $E$.
Each individual has one of three health states defined by $\\{S,I,R\\}$ for
susceptible, infected, and recovered. The health of the network is then
characterized by vector $H\in\\{S,I,R\\}^{|V|}$. At the beginning of a
trajectory, a random individual in $N$ gets infected. For each time step, the
infection spreads from an infected individual to a susceptible individual $v$
under $p^{v}_{S\rightarrow I}=1-(1-\tau)^{\\#I(v,N)}$, where $\tau\in[0,1]$ is
the probability of spreading and $\\#I(v,N)$ is the number of infected
neighbors of susceptible individual $v$ in $N$. Then, probability of recovery
is given by $p_{I\rightarrow R}=\rho$. At each time step, the agent is able to
allocate one vaccine to give to an individual. Any individual can receive an
unrestricted number of vaccinations, but vaccinating an individual will only
have an effect if they are in the susceptible state. Vaccinations do not roll
over over time steps, but the agent is able to choose not to vaccinate anyone
at a time step. The reward function promotes the healthiness of a population
and is given $r(s_{t})=\zeta_{0}\cdot(\sum_{i=1}^{|V|}\mathds{1}(H_{it}\neq
I))/|V|$.

We define the notion of a community in $N$ by applying the Girvan-Newman
algorithm [18] on the graph. This community detection algorithm progressively
removes edges from the graph by betweenness, which is the number of shortest
paths between two nodes that travel through an edge. We apply this algorithm
once to obtain two communities (visualized in the Appendix).

#### Fairness Constraint.

The fairness constraint is defined as

$\Delta(s_{t})=\text{max}_{c,c^{\prime}}\bigg{|}\frac{\sum_{t}\text{vaccinations
given}_{ct}}{\sum_{t}\text{newly
infected}_{ct}+1}-\frac{\sum_{t}\text{vaccinations
given}_{c^{\prime}t}}{\sum_{t}\text{newly infected}_{c^{\prime}t}+1}\bigg{|},$
(5)

where $c$ is a community. This fairness constraint is inspired by that from
the attention allocation problem, and focuses on minimizing the differences in
the ratio of vaccinations to newly infected individuals over time across
communities.

#### Agents.

The PPO agent observation is the health states $H$ of the network. The action
is a number $\\{1,2,...,|V|\\}\cup\\{\varnothing\\}$ where $\varnothing$
corresponds to not vaccinating anyone. We again use the three previously
defined PPO agents (G-PPO, R-PPO, A-PPO). Similar to the previous case study,
a min-max normalization is applied to each term in Equation 3 for A-PPO. We
define two variations of the human-designed policies in [16]. First, the
random baseline will randomly select a susceptible individual to vaccinate,
and if there are no more susceptible individuals, then it will try to
vaccinate someone randomly in the graph regardless of status. We also define
the max neighbor (denoted as "Max") baseline that will vaccinate susceptible
individuals sorted by number of neighbors in the graph, and do the same for
non-susceptible individuals if there are no more susceptible individuals in
the graph.

#### Results.

Figure 3: The reward over time and delta plots generated by evaluating on the
precision disease control environment for 200 trials. We observe that all PPO
policies outperform the baseline policies, with both A-PPO and R-PPO being
equally the most fair.

We run experiments on the Karate Club graph for 20 time steps per trajectory
with $\tau=0.5$ and $\rho=0.005$. We set the initially infected individual to
be the most connected node in the graph for the most interesting results, and
impose a burn-in period where the infection is allowed to freely spread for
one time step.

As seen in Figure 3, the PPO agents again outperform the baseline agents in
reward and fairness. A-PPO and R-PPO both collect an equal amount of rewards,
with R-PPO being slightly more favorable. The G-PPO and max agents’ rewards
fall off as they fail to satisfy the fairness evaluation objective over time.
We observe that the random agent begins with a lower reward, but increases
over time, which can be explained by the fairness analysis next. The CPO agent
is observed to actually perform the worst in terms of utility. In Figure 3,
A-PPO and R-PPO are also the most fair, as they both quickly drive the
fairness constraint toward zero over time. The random agent is the next
fairest agent, which can be explained by the fact that the random agent does
not discriminate between groups when deciding who to vaccinate next. The G-PPO
and max agents actually increase linearly in delta over time, which also makes
sense since neither agent is constrained for fairness. Although CPO did not
perform well in reward, it is actually one of the most fair agents evaluated
here.

This experiment provides an additional insight into how RL agents can
outperform human-designed policies. Here, we observe that A-PPO and R-PPO
outperform all other agents in terms of reward and fairness. Although
advantage regularization appears to not have any significant improvement over
fairness constraining at the reward level, this experiment still serves as an
example for how our approach can perform at least as well as reward-only
fairness constraining, and how it can be more robust of a procedure than CPO.

##  5 Conclusion

We proposed new methods to design fairness-constrained decision-based neural
control policies in long-term fairness problems. We augmented our approach
with advantage regularization by formulating fairness as a stability property
within policy optimization. We demonstrated the benefits of these methods in
several dynamic environments for long-term fairness. Future work includes
extending this framework to other policy optimization algorithms and
investigating how our approach can be extended with stricter fairness-
constrained methods.

We remark that our approach only guarantees optimality under the definitions
of the objective and the fairness constraints, and the optimal way to minimize
this constraint does not necessarily correspond to the most socially
acceptable way to solve long-term fairness problems. Thus, fairness obtained
through our proposed methods is limited to the design formulation of the long-
term fairness problem. Consequently, it is vital to correctly formulate the
objectives and fairness requirements while being aware of how the fairness
requirements imposed on the policy may induce unexpected and potentially
unfair behaviors from a different perspective.

##  6 Acknowledgement

This material is based on work supported by DARPA Contract No.
FA8750-18-C-0092, AFOSR YIP FA9550-19-1-0041, NSF Career CCF 2047034, NSF CCF
DASS 2217723, and Amazon Research Award. We appreciate the valuable feedback
from Ya-Chien Chang, Milan Ganai, Chiaki Hirayama, Chenning Yu, Hongzhan Yu,
Yaoguang Zhai, Ruipeng Zhang, and the anonymous reviewers.

## References

  * [1] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel.  Constrained policy optimization.  In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 22–31. JMLR. org, 2017.
  * [2] Eitan Altman.  Constrained Markov decision processes, volume 7.  CRC Press, 1999.
  * [3] James Atwood, Hansa Srinivasan, Yoni Halpern, and David Sculley.  Fair treatment allocations in social networks.  CoRR, abs/1911.05489, 2019.
  * [4] Ruxandra Bobiti and Mircea Lazar.  Automated sampling-based stability verification and doa estimation for nonlinear systems.  IEEE Transactions on Automatic Control, PP:1–1, 01 2018.
  * [5] Steven Bohez, Abbas Abdolmaleki, Michael Neunert, Jonas Buchli, Nicolas Heess, and Raia Hadsell.  Value constrained model-free continuous control.  arXiv preprint arXiv:1902.04623, 2019.
  * [6] Ya-Chien Chang and Sicun Gao.  Stabilizing neural control using self-learned almost lyapunov critics.  In IEEE International Conference on Robotics and Automation, ICRA 2021, Xi’an, China, May 30 - June 5, 2021, pages 1803–1809. IEEE, 2021\.
  * [7] Ya-Chien Chang, Nima Roohi, and Sicun Gao.  Neural lyapunov control.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 3240–3249, 2019.
  * [8] Jingdi Chen, Yimeng Wang, and Tian Lan.  Bringing fairness to actor-critic reinforcement learning for network utility optimization.  In IEEE INFOCOM 2021 - IEEE Conference on Computer Communications, pages 1–10, 2021.
  * [9] Jianfeng Chi, Jian Shen, Xinyi Dai, Weinan Zhang 0001, Yuan Tian 0001, and Han Zhao 0002.  Towards return parity in markov decision processes.  In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 1161–1178. PMLR, 2022.
  * [10] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone.  Risk-constrained reinforcement learning with percentile risk criteria.  The Journal of Machine Learning Research, 18(1):6070–6120, 2017\.
  * [11] Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh.  A lyapunov-based approach to safe reinforcement learning.  In Advances in neural information processing systems, pages 8092–8101, 2018.
  * [12] Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh.  Lyapunov-based safe policy optimization for continuous control.  arXiv preprint arXiv:1901.10031, 2019.
  * [13] Sam Corbett-Davies and Sharad Goel.  The measure and mismeasure of fairness: A critical review of fair machine learning.  arXiv preprint arXiv:1808.00023, 2018.
  * [14] Elliot Creager, David Madras, Toniann Pitassi, and Richard Zemel.  Causal modeling for fairness in dynamical systems.  In Proceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020.
  * [15] Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa.  Safe exploration in continuous action spaces.  arXiv preprint arXiv:1801.08757, 2018.
  * [16] Alexander D’Amour, Hansa Srinivasan, James Atwood, Pallavi Baljekar, D. Sculley, and Yoni Halpern.  Fairness is not static: deeper understanding of long term fairness via simulation studies.  In Mireille Hildebrandt, Carlos Castillo, L. Elisa Celis, Salvatore Ruggieri, Linnet Taylor, and Gabriela Zanfir-Fortuna, editors, FAT* ’20: Conference on Fairness, Accountability, and Transparency, Barcelona, Spain, January 27-30, 2020, pages 525–534. ACM, 2020.
  * [17] Yingqiang Ge, Shuchang Liu, Ruoyuan Gao, Yikun Xian, Yunqi Li, Xiangyu Zhao, Changhua Pei, Fei Sun, Junfeng Ge, Wenwu Ou, and Yongfeng Zhang.  Towards long-term fairness in recommendation.  pages 445–453, 03 2021.
  * [18] M. Girvan and M. E. J. Newman.  Community structure in social and biological networks.  Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002.
  * [19] Wassim Haddad and Vijaysekhar Chellaboina.  Nonlinear dynamical systems and control: A lyapunov-based approach.  Nonlinear Dynamical Systems and Control: A Lyapunov-Based Approach, 01 2008.
  * [20] Moritz Hardt, Eric Price, Eric Price, and Nati Srebro.  Equality of opportunity in supervised learning.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
  * [21] Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan.  The disparate effects of strategic manipulation.  In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* ’19, page 259–268, New York, NY, USA, 2019. Association for Computing Machinery.
  * [22] Lydia T. Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt.  Delayed impact of fair machine learning.  In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 6196–6200. International Joint Conferences on Artificial Intelligence Organization, 7 2019\.
  * [23] Shenyu Liu, Daniel Liberzon, and Vadim Zharnitsky.  Almost lyapunov functions for nonlinear systems.  Automatica, 113:108758, 2020.
  * [24] Masoud Mansoury, Himan Abdollahpouri, Mykola Pechenizkiy, Bamshad Mobasher, and Robin Burke.  A graph-based approach for mitigating multi-sided exposure bias in recommender systems.  ACM Trans. Inf. Syst., 40(2), nov 2021.
  * [25] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.  A survey on bias and fairness in machine learning.  ACM Comput. Surv., 54(6):115:1–115:35, 2021.
  * [26] Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt.  The social cost of strategic classification.  In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* ’19, page 230–239, New York, NY, USA, 2019. Association for Computing Machinery.
  * [27] Hossam Mossalam, Yannis M Assael, Diederik M Roijers, and Shimon Whiteson.  Multi-objective deep reinforcement learning.  arXiv preprint arXiv:1610.02707, 2016.
  * [28] Pegah Nokhiz, Aravinda Kanchana Ruwanpathirana, Neal Patwari, and Suresh Venkatasubramanian.  Precarity: Modeling the Long Term Effects of Compounded Decisions on Individual Instability, page 199–208.  Association for Computing Machinery, New York, NY, USA, 2021.
  * [29] Alexander Pan, Kush Bhatia, and Jacob Steinhardt.  The effects of reward misspecification: Mapping and mitigating misaligned models.  In International Conference on Learning Representations, 2022.
  * [30] Spencer M. Richards, Felix Berkenkamp, and Andreas Krause.  The lyapunov neural network: Adaptive stability certification for safe learning of dynamic systems.  ArXiv, abs/1808.00924, 2018.
  * [31] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347, 2017.
  * [32] Umer Siddique, Paul Weng, and Matthieu Zimmer.  Learning fair policies in multiobjective (deep) reinforcement learning with average and discounted rewards.  In Proceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020.
  * [33] Chen Tessler, Daniel J Mankowitz, and Shie Mannor.  Reward constrained policy optimization.  arXiv preprint arXiv:1805.11074, 2018.
  * [34] Ming Yu, Zhuoran Yang, Mladen Kolar, and Zhaoran Wang.  Convergent policy optimization for safe reinforcement learning.  In Advances in Neural Information Processing Systems, pages 3121–3133, 2019.
  * [35] Xueru Zhang, Ruibo Tu, Yang Liu, Mingyan Liu, Hedvig Kjellström, Kun Zhang, and Cheng Zhang.  How do fair decisions fare in long-term qualification?  In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc.

##  Appendix A An Introduction to Lyapunov Stability

We first define an $n$-dimensional dynamical system $\Phi$ by:

$\dot{x}(t)=f(x(t),u(t)),u(t)=g(x(t))$

where $x(t)\in D$ is a state vector at time $t\in\mathbb{R}$ in the state
space $D\subseteq\mathbb{R}^{n}$, $g:D\rightarrow\mathbb{R}^{m}$ is a control
function, and $f:D\rightarrow\mathbb{R}^{n}$ is a Lipschitz-continuous vector
field.

Suppose system $\Phi$ has an equilibrium point at $x_{e}$. The system is
stable at $x_{e}$ if for all $\epsilon\in\mathbb{R}^{+}$, there exists some
$\delta(\epsilon)\in\mathbb{R}^{+}$ such that $||x(t)-x_{e}||<\epsilon$ for
all $t\geq 0$ if $||x(0)-x_{e}||<\delta$. In other words, if an initial point
$x(0)$ starts at some distance $\delta$ from equilibrium point $x_{e}$, any
point along all possible solution trajectories from $x(0)$ to $x_{e}$ should
be smaller than some distance $\epsilon$ from $x_{e}$. To take this stability
notion one step further, we say system $\Phi$ is locally asymptotically stable
around $x_{e}$ if $\lim_{t\rightarrow\infty}x(t)=0$ for all
$||x(0)-x_{e}||<\delta$.

Next, we explore the definition of the Lyapunov function and Lie derivative.
Using the existing system setup, let $V:D\rightarrow\mathbb{R}$ be a
continuously differentiable function. $V$ is a Lyapunov function if $V(0)=0$
and $L_{f}V(x(t))<0$ and $\forall x\in D\setminus\\{0\\},V(x(t))>0$. The Lie
derivative of $V$ over $f$ is defined:

$L_{f}V(x(t))=\sum^{n}_{i=1}\frac{\partial V}{\partial
t}=\sum^{n}_{i=1}\frac{\partial V}{\partial
x_{i}}\frac{dx_{i}}{dt}=\sum^{n}_{i=1}\frac{\partial V}{\partial
x_{i}}\dot{x}(t)$

At a high level, the Lyapunov function $V$ defines a field of attraction
around some equilibrium point, and the Lie derivative $L_{f}V(x(t))$ measures
the rate of convergence of V over time along the system dynamics of $x(t)$ to
its equilibrium point $x_{e}$. If this Lyapunov function can be defined,
system $f$ is asymptotically stable at $x_{e}$.

One issue with formulating the Lie derivative in the context of Reinforcement
Learning (RL) training is that computing it requires full access to system
dynamics $f$, which the RL policy in training does not have access to. Thus,
we must approximate the Lie derivative along sampled trajectories of the
dynamical system during training:

$L_{f,\Delta t}V(x(t))=\frac{1}{\Delta t}(V(x(t+1))-V(x(t)))$

where

$\lim_{\Delta t\rightarrow\infty}L_{f,\Delta t}V(x(t))=L_{f}V(x(t))$

##  Appendix B Hyperparameters for Case Studies

We used the following hyperparameters in the training procedures. Table 1,
Table 2 and Table 3 show the hyperparameters used for PPO variations on
attention allocation, lending, and infectious disease control environments,
respectively. Note that for the lending and precision disease control
environments, our hyperparameters are chosen with respect to a min-max
normalization applied to each advantage term.

PPO Agent | $\zeta_{0}$ | $\zeta_{1}$ | $\zeta_{2}$ | $\beta_{0}$ | $\beta_{1}$ | $\beta_{2}$
---|---|---|---|---|---|---
Greedy (G-PPO) | 1 | 0.25 | 0 | 0 | 0 | 0
Reward-Only Fairness Constrained (R-PPO) | 1 | 0.25 | 10 | 0 | 0 | 0
Advantage Regularized (A-PPO) | 1 | 0.25 | 0 | 0.05 | 0.32 | 0.63
Table 1: The hyperparameters used for each PPO variation during training on the base and harder attention allocation environments. PPO Agent | $\zeta_{0}$ | $\zeta_{1}$ | $\beta_{0}$ | $\beta_{1}$ | $\beta_{2}$
---|---|---|---|---|---
Greedy (G-PPO) | 1 | 0 | 0 | 0 | 0
Reward-Only Fairness Constrained (R-PPO) | 1 | 2 | 0 | 0 | 0
Advantage Regularized (A-PPO) | 1 | 0 | 1 | 0.5 | 0.5
Table 2: The hyperparameters used for each PPO variation during training on the lending environment. PPO Agent | $\zeta_{0}$ | $\zeta_{1}$ | $\beta_{0}$ | $\beta_{1}$ | $\beta_{2}$
---|---|---|---|---|---
No Fairness Constraints (N PPO) | 1 | 0 | 0 | 0 | 0
Only Reward Fairness Constraint (R PPO) | 1 | 0.1 | 0 | 0 | 0
Only Advantage Fairness Constraint (A PPO) | 1 | 0 | 0.6 | 0.15 | 0.25
Table 3: The hyperparameters used for each PPO variation during training on
the precision disease control environment.

##  Appendix C Social network for Infectious Disease Case Study

Figure 4: [Left] Node betweenness centrality visualized for the Karate Club
graph in the precision disease control environment, where the intensity of the
node positively correlates with its betweenness centrality value. [Right]
Communities for the Karate Club graph in the precision disease control
environment. These communities are obtained by applying the Girvan-Newman
community detection algorithm once on the graph.

We obtain our notion of a community in the Karate Club graph using the Girvan-
Newman community detection algorithm. We define edge betweenness as the number
of shortest paths between two nodes that travel through an edge. In this
algorithm, each edge is computed for its edge betweenness. Then, the edge with
the highest betweenness is removed to reveal two communities seen on the right
in Figure 4. Node betweenness centrality is defined as the combined fraction
of all shortest paths between pairs that pass through a node, and can be
visualized on the left in Figure 4. Although betweenness centrality is
distinct from edge betweenness and is not a part of the Girvan-Newman
algorithm, we include it to provide more insight into the underlying structure
of the Karate Club Graph.


# Resistive threshold logic

A. P. James, L.V.J. Francis and D. Kumar

###### Abstract

We report a resistance based threshold logic family useful for mimicking brain
like large variable logic functions in VLSI. A universal Boolean logic cell
based on an analog resistive divider and threshold logic circuit is presented.
The resistive divider is implemented using memristors and provides output
voltage as a summation of weighted product of input voltages. The output of
resistive divider is converted into a binary value by a threshold operation
implemented by CMOS inverter and/or Opamp. An universal cell structure is
presented to decrease the overall implementation complexity and number of
components. When the number of input variables become very high, the proposed
cell offers advantages of smaller area and design simplicity in comparison
with CMOS based logic circuits.

##  1 Introduction

Logic gates implement boolean algebraic expressions obtained from truth
tables. Increase in functional requirements of digital IC’s such as in
microprocessors and ASIC’s results in complex logic state implementations. A
complex set of logic states when represented as a truth table would have large
number of input and output variables. As the number of input variables
increases, it is often not possible to manually reduce the boolean logic
expressions to reduce the number of components required for its
implementation. The most common approach to reduce the number of components
required with a large number of variables is by using logic minimisation based
on prime implicant logics. Technique such as Karnaugh map[1],
QuineMcCluskey[2], Petrick’s method, Buchberger’s algorithm [3] and Espresso
minimization algorithm [4], are the widely used approaches. However, when the
number of inputs increases significantly, logic minimisation methods become
inefficient. In addition, implementations using existing logic families become
challenging as they are often restricted by the gate delays, the number of
inputs and the number of components.

The common approach employed to implement boolean algebra with a large number
(>10) of variables, is to apply the minimization techniques for standard gates
with a limited number of inputs (<10). This always results in more number of
circuit components than that was possible with gates that could support as
many number of inputs as the number of variables. In addition to this issue,
the number of components required to implement a gate vary from one boolean
logic to another, which results in increased structural complexity and results
in increased investment in production scale verification and testing cycles.

Generic digital circuits such as a single 2n to 1 multiplexer can be used to
implement $n$-input boolean logic function in canonical sum-of-products form.
As the number of inputs to the multiplexer increases, a typical AND-OR logic
would have large number of inputs per gate for its implementation. In order to
implement large variable boolean logic functions such as using multiplexers,
we introduce the concept of resistance threshold logic that minimises number
of components and design complexity. The proposed resistive threshold logic is
made up of a resistive divider and a threshold logic circuit. The idea of such
an analog-binary cell is inspired from the implementation challenges of the
long established theory and practices of neuron cell modelling and logic
circuits [5]. Conventional neuron inspired logic gate implementations[6] are
complex due to the requirements of multi-valued weights and neuron like
threshold functions. In addition, they fail to meet the original aim of having
large input logic gates useful for mimicking brain like logic functions. In
contrast, the resistive threshold logic is aimed to be simple in structure
having the ability to realise large variable logic functions, and is intended
to be used as a new standard cell universal logic family with a possible
ability to mimic brain logic.

##  2 Proposed Cell

Figure 1: The circuit diagram of the proposed resistive divider boolean logic
cell that consists of a two input resistive divider and a variable threshold
CMOS inverter is presented.

The proposed logic cell shown in Fig. 1 consists of a resistive divider and a
variable threshold inverter. In contrast to the earlier reported work on
cognitive memory network [7], in this work, we propose a significantly
different configuration, implementation and application of the structurally
similar and conceptually different cell. The input to the resistive divider
are the digital values that can be equated to the logic inputs of a digital
logic gate. Based on the output of the resistive divider and a predefined
inverter threshold, we propose to implement the basic boolean logic functions.
The selection of the threshold and the use of resistive logic in designing a
generalized logic cell is the primary contribution of this research.

An $N$-input resistance divider circuit consists of $N$ input resistors
$R_{i}$ and one reference resistor $R_{0}$. The output voltage $V_{0}$ for
$N$-input voltages $V_{i}$ can be represnted as
$V_{0}={\sum_{i=1}^{N}\frac{V_{i}}{R_{i}}}/{(\frac{1}{R_{0}}+\sum_{i=1}^{N}\frac{1}{R_{i}})}$.
The inputs $V_{i}$ have either of the two logical levels $V_{H}$ or $V_{L}$,
representing a binary logic [1,0]. We keep equal values to $R_{i}^{\prime}s$
and $R_{0}=mR_{i}$, which results in:
$V_{0}=\frac{\sum_{i=1}^{N}{V_{i}}}{\frac{1}{m}+{N}}$.

A straight forward approach to implement resistors is by using semiconductor
resistors. Semiconductor resistors consist of a resistive body that is
surrounded by an insulator often developed over a substrate, and two terminal
contacts implemented using conductive metallic strips. The value of
semiconductor resistance can be obtained from the expression, $\frac{\rho
L}{x_{j}W}$, where $\rho$ is the resistivity, $L$ is the length, $x_{j}$ is
the layer thickness and $W$ is the width of the resistive body.

Figure 2: The impact of change in input resistance on the output voltage
$V_{0}$ of the resistive divider is graphically illustrated. The results are
demonstrated for 100 input resistive divider, with each line showing the
relative change in $V_{0}$ for the corresponding number of resistors are
uniformly perturbated within a $\pm 10\%$ tolerance level of resistor values.
Note: here we keep $V_{i}=1$.

A concern while using resistance devices (such as semiconductor resistors) is
the impact of change in resistance value due to second order implementation
effects, such as improper junctions and defects. Figure 2 shows a simulated
study of the impact of change in resistance values on the output voltage of a
resistive divider circuit. It is assumed here that the changes in the resistor
values are limited within a tolerance level of $\pm 10\%$ of the actual
resistive values. It can be seen that a maximum of $\pm 10\%$ resistive values
introduces only about $.0894\%$ change in output voltage, which makes the
practical implementation of the resistive divider feasible even under
realistic conditions. While using semiconductor resistors, when the number of
inputs increase, the leakage current through the semiconductor resistance
becomes prohibitively high. This drawback is overcome by replacing
semiconductor resistors with memristors [8], which has negligible amount of
leakage current.

The proposed resistive divider circuit uses the memristor modeled by HP [8].
The device has a thin film of titanium dioxide (TiO2) sandwiched between two
platinum terminals. The titanium dioxide layer is doped on one side with
oxygen vacancies, TiO2-x. The doped region has lower resistance than that of
the insulated undoped region. The boundary between doped and undoped region
determines the effective resistance of the device. Let $D$ be the total width
of the TiO2 layer and $W$ be the width of the doped TiO2 layer. When a
positive voltage is applied at the doped side, the oxygen vacancies moves
towards the undoped region, increasing the width of the doped region, $W$ and
hence the effective resistance of the memristor decreases. The effective
resistance $M_{eff}$ of the memristor is
$M_{eff}=\frac{W}{D}R_{ON}+(1-\frac{W}{D})R_{OFF}$, where, $R_{ON}$ (=1
k$\Omega$) is the resistance of the memristor if it is completely doped and
$R_{OFF}$ (=100 k$\Omega$) is the resistance of the memristor if it is
undoped. When input voltage is withdrawn or when there is no potential
difference between the terminals, the memristor maintains the boundary between
the doped and undoped region, since the oxygen ions remain immobile after
removal of the input voltage. Thus the resistance will be maintained at the
same value before withdrawing the input voltage. From the equation,
$i=\frac{v}{M(q)}$ [9], where $v$ and $i$ are the voltage and current across
the memristor, and $M(q)$ is charge dependent resistance of the memristor, we
can see that when the voltage difference across the memristor is $0$, the
current through the memristor is $0$. If there is a reverse potential across
the memristor, the width of the undoped region increases, resulting in an
increase in the effective resistance of the memristor. This high resistance
will block the reverse leakage current through the memristor. When the number
of inputs increases, the collective forward current through the circuit does
not increase significantly, since the effective resistance in the memristor is
constant. Table 1 shows the effect of increase in number of inputs on the
collective current flowing through the circuit.

Table 1: Effect of increase in number of inputs on the forward current flowing through the memristor in the circuit. Number of inputs |  Current through a single memristor |  Current through the potential divider circuits
---|---|---
2 |  3.33$\mu$A |  6.66$\mu$A
10 |  0.909$\mu$A |  9.09$\mu$A
100 |  0.99099nA |  9.90099$\mu$A
Table 2: Truth Table of Two Input Resistive Divider Logic Cell When Used as NAND and NOR Gates  Input Voltage ($V_{i}$) |  Output Voltage |  NANDa |  NORb
---|---|---|---
$V_{1}$ |  $V_{2}$ |  $V_{0}$ |  |
$V_{L}$ |  $V_{L}$ |  $\frac{2V_{L}}{3}$ |  $V_{H}$ |  $V_{H}$
$V_{L}$ |  $V_{H}$ |  $\frac{V_{L}+V_{H}}{3}$ |  $V_{H}$ |  $V_{L}$
$V_{H}$ |  $V_{L}$ |  $\frac{V_{L}+V_{H}}{3}$ |  $V_{H}$ |  $V_{L}$
$V_{H}$ |  $V_{H}$ |  $\frac{2V_{H}}{3}$ |  $V_{L}$ |  $V_{L}$
a NAND threshold range $\frac{V_{L}+V_{H}}{3}<V_{th}<\frac{2V_{H}}{3}$
b NOR threshold range $\frac{2V_{L}}{3}<V_{th}<\frac{V_{L}+V_{H}}{3}$

Table 2 shows the truth table of the two input resistive divider logic cell,
that implements the NAND and NOR gates using a predefined inverter threshold
$V_{th}$. Assuming that $V_{dd}=1V,V_{H}=1V,V_{L}=0V$ it is clear from Table 2
that if the threshold voltage of the inverter is set between $0V$ and $1/3V$,
the cell will work as NOR logic and if it is between $2/3V$ and $1/3V$ the
cell will work as NAND logic. That means by varying the threshold voltage of
the inverter, NAND and NOR logic can be implemented using a single cell. In
general, the range of threshold voltage, $V_{th}$ of NOR gate is
$\frac{NmV_{L}}{1+Nm}\leq V_{th}\leq\frac{(V_{H}+(N-1)V_{L})m}{Nm+1}$ , and
NAND gate is, $\frac{m(V_{L}+(N-1)V_{H})}{(Nm+1)}\leq
V_{th}\leq\frac{mNV_{H}}{Nm+1}$. To find the $m$ value, the lower limit of
NAND gate threshold range $(\frac{m(V_{L}+(N-1)V_{H})}{(Nm+1)})$ is equated to
$\frac{V_{H}+V_{L}}{2}$. Now if we assume $V_{L}$ as $0V$ then we get the $m$
value as$\frac{1}{N-2}$ and we can say that the threshold voltage of NAND gate
must be between $\frac{V_{H}+V_{L}}{2}$ and $\frac{mNV_{H}}{Nm+1}$.

The threshold voltage of the MOSFET is dependent on several parameters such as
substrate bias voltage $V_{bs}$, the surface potential $\phi_{s}$, and
substrate doping concentration [10]. The threshold voltage $V_{tn}$ of the
MOSFET can be varied by changing its substrate bias, $V_{bs}$. The dependence
of substrate bias and the threshold voltage is expressed as,
$V_{tn}=V_{tn0}+K_{1}(\sqrt{\phi_{s}-V_{bs}}-\sqrt{\phi_{s}})+C$ , where,
$V_{tn0}$ is the zero bias threshold voltage, the surface potential
$\phi_{s}=2\frac{k_{B}T}{q}\ln(\frac{N_{a}}{n_{i}})$, $K_{1}$ is a parameter
derived by considering non-uniform doping and short channel effects
$K_{1}=\gamma_{2}-2K_{2}\sqrt{\phi_{s}-V_{bm}}$ where
$K_{2}=\frac{(\gamma_{1}-\gamma_{2})(\sqrt{\phi_{s}-V_{b}x}-\sqrt{\phi_{s}})}{2\sqrt{\phi_{s}}(\sqrt{\phi_{s}-V_{bm}}-\sqrt{\phi_{s}})+V_{bm}}$
$\gamma_{1}$ and $\gamma_{2}$ are body bias coefficient when substrate doping
concentration are equal to $N_{ch}$ and $N_{sub}$ respectively.
$\gamma_{1}=\frac{\sqrt{2q\epsilon_{Si}N_{ch}}}{C_{ox}},\gamma_{2}=\frac{\sqrt{2q\epsilon_{Si}N_{sub}}}{C_{ox}}$
and $V_{bm}$ is the maximum substrate bias voltage. And $C$ shows the effect
of narrow channel on threshold voltage. The threshold voltage of the inverter
can be represented as,
$V_{th}=\left({(V_{tn}+(V_{DD}-|V_{tp}|))\sqrt{\frac{\mu_{p}W_{p}}{\mu_{n}W_{n}}}}\right)/\left({1+\sqrt{\frac{\mu_{p}W_{p}}{\mu_{n}W_{n}}}}\right)$,
which shows the role of the threshold voltages of the MOSFETs in determining
the threshold of the inverter.

Figure 3: The relation between Output voltage of the inverter and Output
voltage of the resistive divider, for 10 input and 20 input boolean logic,
when it is working as a NOR gate is shown

Fig. 3 shows the relationship between the output voltage of the resistive
divider cell (input to the inverter) and the output voltage of an inverter,
for 10 input and 20 input situations, when the cell is working in NOR logic.
$V_{0}$ value when the inputs are $V_{1}=1$ and $V_{2}=V_{3}=..V_{10}=0$ is
$0.0556V$, and when $V_{1}=V_{2}=..V_{10}=0$ is $0$, so the threshold voltage
of the inverter must be between $0$ and $0.0556$, to work as a NOR logic.
Similarly for 20 input boolean logic, the threshold voltage of the inverter
must be between $0$ and $0.026$. This shows that if the threshold voltage of
the inverter can be lowered to a very small value we can implement resistive
threshold logic with large number of inputs.
In order to reduce the threshold voltage, here we introduced three inverters
with three different $V_{DD}$’s. Fig. 4 shows a universal gate structure which
can be used to implement AND, NAND, OR, NOR and NOT logic. For the cell to
work as a NAND logic, the switches $S_{1}$ and $S_{4}$ are closed, and the
output is taken from $V_{out}$. So in this case, three inverters will be
enabled. To implement AND logic, the switches $S_{1}$ and $S_{3}$ are closed,
and the output is taken from $\overline{V_{out}}$. For the AND logic, two
inverters need to be enabled. If the switches $S_{2}$ and $S_{4}$ are closed,
we get a NOR logic from $V_{out}$, here only one inverter has to be enabled.
If both $S_{2}$ and $S_{3}$ are closed, OR logic can be implemented, here two
inverters are used. The approach shown in Fig. 4, demonstrates the concept of
generalization of resistive threshold logic cell to implement the most basic
boolean logic functions. To maintain practical relevance of the approach all
the results reported are based on device parameters from 0.25$\mu m$ TSMC
process. Note that as $V_{DD}$ decreases $V_{th}$ also decreases. When
$V_{DD}$ changes the $V_{GS}$ of PMOS in the CMOS inverter will also change.
As a result, in the case of the proposed cell with 10 inputs, the PMOS will be
in cut off state when the input condition is $V_{1}=1$ and
$V_{2}=V_{3}=..V_{10}=0$ and we get a low level output from the 1st inverter.
Since the 1st inverter can only provide a high value of $0.25V$, we use other
two inverters in order to get a high value of $1V$. The working of the
proposed cell in Fig. 4 as a NAND or NOR gate purely rests on the values of
$V_{tn}$ and $V_{th}$ of the inverter, for a given number of inputs.

Figure 4: The circuit diagram to implement NAND, NOR, AND, OR and NOT logic
functions consisting of memristive resistance divider and CMOS inverters with
three different power supply values.

If $V_{H}$ is set as $1V$ and $V_{L}$ as $0$, then the threshold voltage
$V_{th}$ range for NAND gate must be between $0.5V$ and the $V_{0}$ value
obtained when all inputs are $V_{H}$. Figure 5 shows the relationship that
exists between $V_{tn}$ and $V_{th}$ to implement the proposed cell as NAND
gate, as the number of inputs changes from 3 to 100. For each number of inputs
the $V_{th}$ is calculated for a particular $V_{tn}$ and with a fixed
$V_{tp}$, $W_{p}$, $\mu_{p}$, $W_{n}$, $\mu_{n}$ and $V_{DD}$ values. For a
given number of inputs the threshold voltage is above $0.5V$, so by using a
single inverter with $V_{DD}$ as $1V$, NAND logic can be implemented. That
means NAND logic can be implemented using the proposed cell with one inverter
such as in Fig. 1. Using three inverters with different $V_{DD}$, a 100 input
NOR logic can be realised. For implementing NOR logic, for larger number of
inputs, the threshold voltage of the inverter circuit has to be reduced to a
very low value. This problem can be overcome by boosting the signal, using an
Opamp amplifier, before applying to the inverter. Table 3 shows the leakage
power and the spectral noise due to Johnson, shot and flicker noise in
multi-$V_{DD}$ logic proposed in Fig 4. The the maximum noise levels are very
low (ie in nV) relative to signal reference of 1V range.

Table 3: Leakage power and noise spectral density for 100 input gate proposed multi-$V_{DD}$ gate configuration in Fig 4 Performance measure | NAND | AND | NOR | OR
---|---|---|---|---
Noise spectral density per unit square root bandwidth ($nV/Hz^{1/2}$) | 7.94 | 9.75 | 75.71 | 10.15
Leakage power ($nW$) | 0.014 | 0.017 | 0.967 | 0.971
Figure 5: A graph indicating the dependence of threshold voltage of the CMOS
inverter and threshold voltage of the NMOS. The threshold values shown in the
graph is a result of changing the number of inputs from 3 to 100 and
calculating the minimum inverter threshold voltages required to implement the
circuit as a NAND gate Figure 6: The universal gate structure that implements
NAND, NOR, AND, OR and NOT logic functions using memristive resistance divider
and Opamp threshold circuit.

The universal circuit in Fig 4 is modified to incorporate Opamp threshold
logic as shown in Fig. 6. The threshold logic when implemented using Opamp
[11], offers the advantage of scalability over increase in number of inputs.
The Opamp is designed using 8 MOSFETs and in the same technology as that of
the CMOS NOT gate. The Opamp reference voltage for NOR logic, $V_{REF}$ is
fixed as $V_{L}+\delta$ and for NAND logic, $V_{REF}$ is fixed as
$V_{H}-\delta$, where $\delta$ is small voltage defined to ensure the bounds
of $V_{th}$. The Opamp shifts the voltage to a high value or low value
depending on the input voltage, $V_{0}$. It also acts as a buffer helping to
isolate the inputs from the output enabling realistic implementations of very
large of inputs per gate.

###  2.1 Comparisons

Fig. 7 indicates the area required to implement NOR and NAND universal logic
gates for 2, 10, and 1000 input logic gates implemented using CMOS logic, and
that using the resistive threshold logic. In implementing CMOS logic the
maximum number of inputs per gate is taken as 5. The Fan in of the proposed
cell using Opamp is very high ($=14.498\times 10^{6}$), indicating that we can
implement a large variable boolean logic using a single resistive divider
cell. For increasing number of inputs, the proposed cells contain lesser
number of components and area, when compared to the CMOS logic. Since CMOS
based logic gates are practically limited to small number of inputs, we have
used a layered combination of 5 input gates to implement gates with 10 or more
inputs. Table 4 compares the power dissipation of the proposed logic with that
of CMOS logic for NAND and NOR gates. CMOS gates dissipates lesser power as
against its memristive counterparts. The use of low power memristive
devices[12] would be required to reduce the power dissipation. Table 5 shows
the comparison of the noise margin of the logic families for single input NAND
and NOR logic, indicating that the proposed logic has comparable noise
tolerance levels to that with the existing techniques. In addition, the
averaging nature of the potential divider can further help to increase the
noise tolerance levels than specified through noise margins. Table 6 shows a
comparison of propagation delay when a square pulse with 40$\mu$s time period
and 50% duty cycle is applied. The resistive threshold logic shows better
response when the number of inputs become very high, and when with lower
number of inputs show comparable delays.

Figure 7: The bar graph shows the area comparison of CMOS with that of Resistive Threshold Logic (with Opamp threshold circuit, Fig. 6), using NAND and NOR gate implementations. Table 4:  Comparison of the Resistive Logic with CMOS Logic Logic familya |  Logic function | Power Dissipation
---|---|---
|  |  10 i/p |  100i/p
CMOS logic |  |  0.009nW |  0.036nW
Resistive logic (Opamp threshold) |  NOR |  10.6$\mu$W |  11.49$\mu$W
CMOS logic |  |  0.062nW |  0.753nW
Resistive logic (Opamp threshold) |  NAND |  9.2$\mu$W |  10.09$\mu$W
aThe technology size of all the components in the circuit is kept same for all
the gates for fairness in comparison.

As the resistance elements does not significantly introduce the delay with
increase in number of inputs, a large number of inputs (>100) is practically
possible for the proposed cell. In contrast with the existing technologies
that are practically limited to about 5-10 inputs per gate, the ability of the
proposed resistive threshold logic to handle large number of inputs reduces
the complexity of the design and layout of the large variable digital
circuits.

Table 5: Noise margin of different logic families Logic families | NAND | NOR
---|---|---
|  NML |  NMH |  NML |  NMH
CMOS |  0.363V |  0.587V |  0.233V |  0.616V
Pseudo NMOS |  0.429V |  0.413V |  0.276V |  0.461V
Domino CMOS |  0.407V |  0.376V |  0.104V |  0.43V
Resistive logic |  0.369V |  0.558V |  0.132V |  0.777V
Table 6: Propagation delay of different logic families for different number of inputs Logic families | NAND delay | NOR delay
---|---|---
|  3i/p |  10i/p |  1000i/p |  3i/p |  10i/p |  1000i/p
CMOS |  0.47$\mu$s |  0.54$\mu$s |  0.65$\mu$s |  0.50$\mu$s |  0.52$\mu$s |  0.66$\mu$s
Pseudo NMOS |  0.48$\mu$s |  0.60$\mu$s |  0.85$\mu$s |  0.51$\mu$s |  0.58$\mu$s |  0.72$\mu$s
Domino CMOS |  0.48$\mu$s |  0.51$\mu$s |  0.75$\mu$s |  0.51$\mu$s |  0.58$\mu$s |  0.75$\mu$s
Resistive logic (Opamp threshold) |  0.45$\mu$s |  0.45$\mu$s |  0.45$\mu$s |  0.60$\mu$s |  0.60$\mu$s |  0.60$\mu$s

###  2.2 Example Circuits

The proposed logic is compared with the CMOS implementation using a 16 bit
adder and a 16x1 MUX. The simulation were performed in spice using feature
size of 0.25$\mu$m TSMC process BSIM models and HP memristor model. A ripple
carry adder without applying reduction technique is implemented using 16
single bit adders. The single bit adder require 3 NOT, 3 two input AND, 1
three input OR, 4 three input AND and 1 four input OR gates. Hence, a total of
48 NOT, 24 AND, 16 OR, 64 AND and 16 OR gates are required for the 16 bit
adder. Figure 8 shows an example of 16th output bit of the adder simulated
using input pulses with initial start delay of 10$\mu$s, rise and fall time of
5$n$s, and ON period of either 20$\mu$s or 10$\mu$s with 50% duty cycle.

Figure 8: The signal output of the 16th bit of the designed ripple adder using
the proposed resistive threshold logic. $V_{in}$’s is the inputs,$C_{in}$ and
$C_{out}$ is the input and output carry, and $V_{out}$ the output sum bit.

The 16 bit MUX when using the proposed logic required 16 input OR gate and 5
input AND gates, while CMOS logic required 2, 4 and 5 input AND/OR gates. In
the case of adder, CMOS logic has lesser area in comparison to the resistive
threshold logic, while in 16x1 MUX implementation proposed logic result in
lesser area when compared to CMOS logic. Table 7 demonstrates that when the
number inputs for the AND and OR gates are increased, the proposed logic
require lesser area than its CMOS counterpart. Power dissipation on the other
hand is higher for the proposed logic due to higher forward currents in
memristor as compared with CMOS. This issue can be addressed by using low
power memristors [12] and low power Opamps.

Table 7: Comparison of Circuit Implemented using Resistive Threshold Logic with that of CMOS logic Logic families | 16 bit full adder | 16x1 MUX
---|---|---
|  Power |  Area |  Power |  Area
CMOS logic |  2.5nW |  4.557$\mu$m2 |  0.189nW |  1.070$\mu$m2
Resistive logic (Opamp threshold) |  3.277mW |  8.081$\mu$m2 |  0.447mW |  0.825$\mu$m2
Note:The power dissipation for Opamps in the 16 bit full adder is 2.47mW.

##  3 Conclusion

The concept of resistive threshold logic was presented in an application to
implement conventional digital logic gates. The presented resistive threshold
logic family due to its ability to support large number of inputs can
significantly help reduce the design complexity. Although, the presented
resistive threshold outperforms the conventional CMOS logic implementations in
large input gates in terms of performance parameters such as area, delay and
power, for small input gates further developments on low power and high speed
Opamp designs are required. The CMOS - Resistance Threshold Logic co-design
can optimise the circuit design of conventional CMOS based large variable
boolean logic problems. A disadvantage of the proposed threshold logic using
the memristor technology in [8] as compared with CMOS logic is the higher
power dissipation. However, with the advancements of newer low power
memresitive devices such as [12], the problem of lowering power dissipation to
the levels of CMOS, can be a realistic task. The proposed logic can be
extended to technologies such as carbon nanotubes and organic circuits. In
addition, the ability of the proposed logic to develop large number of input
gates can be seen as an early step in achieving the goal of mimicking brain
like large variable boolean logic applications in VLSI.

## Acknowledgment

The authors would like to thank the anonymous reviewers for their time and
thoughtful review comments, which has resulted in the improvement of overall
quality of the brief.

## References

  * [1] K. Dean, “An extension of the use of karnaugh maps in the minimisation of logic functions,” _Radio and Electronic Engineer_ , vol. 35, no. 5, pp. 294–296, 1968.
  * [2] H. Hwa, “A method for generating prime implicants of a boolean expression,” _IEEE Trasactions on Computers_ , vol. 23, no. 6, pp. 637–641, 1974.
  * [3] L. Bachmair and H. Ganzinger, “Buchberger’s algorithm: A constraint-based completion procedure,” in _First International Conference Constraints in Computational Logics_ , ser. Lecture Notes in Computer Science, vol. 845\. Springer, September 1994, pp. 285–301.
  * [4] P. McGeer, “Espresso-signature: a new exact minimizer for logic functions,” _IEEE Transactions on VLSI_ , vol. 1, no. 4, pp. 432–440, 1993.
  * [5] G. Indiveri, B. Linares-Barranco, T. Hamilton, A. van Schaik, R. Etienne-Cummings, T. Delbruck, S.-C. Liu, P. Dudek, P. H fliger, S. Renaud, J. Schemmel, G. Cauwenberghs, J. Arthur, K. Hynna, F. Folowosele, S. Saighi, T. Serrano-Gotarredona, J. Wijekoon, Y. Wang, and B. K, “Neuromorphic silicon neuron circuits,” _Front. Neurosci._ , vol. 5, no. 73, 2011.
  * [6] V. Beiu, J. M. Quintana, and M. J. Avedillo, “VLSI implementation of threshold logic – a comprehensive survey,” _IEEE Transactions on Neural Networks_ , vol. 14, pp. 1217–1243, September 2003.
  * [7] A. P. James and S. Dimitrijev, “Cognitive memory network,” _Electronics Letters_ , vol. 46, no. 10, pp. 677–678, 2010.
  * [8] R. Williams, “How we found the missing memristor,” _IEEE Spectrum_ , vol. 45, no. 12, pp. 28–35, 2008.
  * [9] Y. Joglekar and S. J. Wolf, “The elusive memristor: properties of basic electrical circuits,” _European J. of Physics_ , vol. 30, pp. 661–675, 2009\.
  * [10] C. H. J. Roth, _Fundementals of Logic Design_ , 4th ed. Pws Pub Co., 1995.
  * [11] P. E. Allen and D. R. Holberg, _CMOS Analog Circuit Design_ , 3rd ed., ser. The Oxford Series in Electrical and Computer Engineering. Oxford University Press, USA, 2011.
  * [12] L. Goux, A. Fantini, G. Kar, Y.-Y. Chen, N. Jossart, R. Degraeve, S. Clima, B. Govoreanu, G. Lorenzo, G. Pourtois, D. Wouters, J. Kittl, L. Altimime, and M. Jurczak, “Ultralow sub-500na operating current high-performance,” in _2012 Symposium on VLSI Technology_ , 2012.