  Many sequential decision making problems, including pool-based active
learning and adaptive viral marketing, can be formulated as an adaptive
submodular maximization problem. Most of existing studies on adaptive
submodular optimization focus on either monotone case or non-monotone case.
Specifically, if the utility function is monotone and adaptive submodular,
\cite{golovin2011adaptive} developed a greedy policy that achieves a $(1-1/e)$
approximation ratio subject to a cardinality constraint. If the utility
function is non-monotone and adaptive submodular, \cite{tang2021beyond} showed
that a random greedy policy achieves a $1/e$ approximation ratio subject to a
cardinality constraint. In this work, we aim to generalize the above mentioned
results by studying the partial-monotone adaptive submodular maximization
problem. To this end, we introduce the notation of adaptive monotonicity ratio
$m\in[0,1]$ to measure the degree of monotonicity of a function. Our main
result is to show that a random greedy policy achieves an approximation ratio
of $m(1-1/e)+(1-m)(1/e)$ if the utility function is $m$-adaptive monotone and
adaptive submodular. Notably this result recovers the aforementioned $(1-1/e)$
and $1/e$ approximation ratios when $m = 0$ and $m = 1$, respectively. We
further extend our results to consider a knapsack constraint. We show that a
sampling-based policy achieves an approximation ratio of $(m+1)/10$ if the
utility function is $m$-adaptive monotone and adaptive submodular. One
important implication of our results is that even for a non-monotone utility
function, we still can achieve an approximation ratio close to $(1-1/e)$ if
this function is ``close'' to a monotone function. This leads to improved
performance bounds for many machine learning applications whose utility
functions are almost adaptive monotone.
