The optimization process and recommendations:

1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.
2. Prefer Inner Join Over Left Join (modified query below): We identified that one or more left joined entities (e.g. `b`) are used in the 'where' clause, in a way that allows to replace it with an optimized inner join. Inner joins can be fully optimized by the database, while Left joins apply limitations on the database's optimizer.
3. Sort and Limit Before Joining (modified query below): In cases where the joins aren't filtering any rows, it's possible to sort and limit the amount of rows using a subquery in the FROM clause, before applying the joins to all other tables.

Optimal indexes for this query:

ALTER TABLE `a` ADD INDEX `a_idx_userid_date` (`userid`,`date`);
ALTER TABLE `a` ADD INDEX `a_idx_date` (`date`);
ALTER TABLE `b` ADD INDEX `b_idx_agencyid` (`agencyid`);

The optimized query:

SELECT
        a_status,
        a_title,
        a_id,
        b.deployed,
        b.accepted,
        b.rejected,
        b.error 
    FROM
        (SELECT
            a.status AS a_status,
            a.title AS a_title,
            a.id AS a_id 
        FROM
            a 
        WHERE
            a.userid = 3 
        ORDER BY
            a.date DESC LIMIT 50) AS a 
    INNER JOIN
        b 
            ON (
                a.a_id = b.id
            ) 
    WHERE
        b.agencyid = 1 
        AND 1 = 1 LIMIT 50